POJ2965 The Pilots Brothers'refrigerator ACM 문제 해결 보고서(귀속+심층검색)


라라라, 나는 맹맹한 초보자이다. 코드를 접한 지 얼마 되지 않아 비교적 보기 흉하게 썼는데, 단지 자신의 회상과 복습을 편리하게 하기 위해서이다.이 문제는 POJ2965입니다. 한 개의 검색 문제는 방법이 비교적 많지만 저는 귀속 검색만 합니다. 문제는 매번 하나의handle를 조작한 다음에 한 줄씩 한 열의handle를 거꾸로 하는 것입니다. 요구는 4*4의 행렬에서 모두 - 시 냉장고를 열어야 한다는 것입니다.뒤집기 수차례는 뒤집기 1회, 뒤집기 짝 수차례는 뒤집기 없는 것과 같다. so는 한 조각당 한 번 뒤집는 상황을 고려하여 폭력적으로 1조각에서 16조각을 뒤집는 상황을 수색한다.

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int result[20],last,b[20],c[20],flag=0;
bool all(int arr[])
{
    for(int i=0;i<16;i++)
    {
        if(arr[i]!=0)
            return false;
    }
    return true;
}
void fan(int arr[],int i)
{
    int x=i/4;
    int y=i%4;
    arr[i]=!(arr[i]);
    for(int j=1;j<4;j++)
    {
        if(x-j>=0) arr[i-4*j]=!(arr[i-4*j]);
        if(x+j<=3) arr[i+4*j]=!(arr[i+4*j]);
        if(y-j>=0) arr[i-j]=!(arr[i-j]);
        if(y+j<=3) arr[i+j]=!(arr[i+j]);
    }
}
void solve(int len,int count,int num)
{
    for(int i=len;i>=count;i--)
    {
        result[count-1]=i-1;
        if(count==1)
        {
            for(int j=0;j<16;j++)
                c[j]=b[j];
            for(int j=num-1;j>=0;j--)
                fan(c,result[j]);
            if(all(c))
            {
                last=num;
                flag=1;
                break;
            }
        }
        else
        {
            solve(i-1,count-1,num);
            if(flag)
                break;
        }
    }
}
int main()
{
    char a[5][5];
    memset(b,0,sizeof(b));
    memset(result,0,sizeof(result));
    for(int i=0;i<4;i++)
    {
        scanf("%s",a[i]);
        for(int j=0;j<4;j++)
            if(a[i][j]=='+') b[i*4+j]=1;
    }
    //for(int i=0;i<16;i++)printf("%d ",b[i]);
    if(all(b))
    {
        printf("0
");
        return 0;
    }
    last=0;
    for(int i=1;i<=16;i++)
    {
        solve(16,i,i);
        if(last==i)
        {
            printf("%d
",last);
            for(int k=0;k<last;k++)
                printf("%d %d
",result[k]/4+1,result[k]%4+1);
            break;
        }
    }
    return 0;
}