12113:Overlapping Squares

Overlapping Squares
나의 사고: 주어진 도형 에 따라 도형 에 포 함 된 사각형 의 개수 와 그들의 각자 의 위 치 를 계산 할 수 있 고 사각형 은 특정한 각 점 의 위치 에 따라 확정 할 수 있 으 며 구체 적 인 방법 은 count () 함 수 를 볼 수 있다.사각형 이 확 정 된 후에 도형 의 각종 변 화 는 사각형 들 의 서로 다른 배치 순서 에 달 려 있다. 모든 배열 을 열거 하고 시 뮬 레이 션 을 해서 시 뮬 레이 션 결과 에 주어진 도형 이 있 는 지 확인 하면 된다.
생각 에 문제 가 없습니다. 코드 를 여러 번 검 사 했 지만 WA 는 아직 문 제 를 발견 하지 못 했 습 니 다. 다시 생각해 보 세 요.

#include
using namespace std;
const int maxn = 10;
const int m = 5, n = 9;
typedef pair P;
P ps[maxn];
int ok = 0;
int ns, vis[maxn], found[m][n];
char G[m][n+5], R[m][n+1];

int count(){
    int cnt = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(i < m-2 && j < n-4 && G[i][j+1] == '_' && G[i+1][j] == '|'){
                found[i][j] =  1;
                ps[cnt++] = P(i, j);
            }
            else if(i < m-2 && j >= 4 && G[i][j-1] == '_' && G[i+1][j] == '|'){
                if(found[i][j-4]) continue;
                found[i][j-4] = 1;
                ps[cnt++] = P(i, j - 4);
            }
            else if(i >= 2 && j < n-4 && G[i][j+1] == '_' && G[i-1][j] == '|'){
                if(found[i-2][j]) continue;
                found[i-2][j] = 1;
                ps[cnt++] = P(i - 2, j);
            }
            else if(i >= 2 && j >= 4 && G[i][j-1] == '_' && G[i-1][j] == '|'){
                if(found[i-2][j-4]) continue;
                found[i-2][j-4] = 1;
                ps[cnt++] = P(i - 2, j - 4);
            }
        }
    }
    return cnt;
}

int DFS(int i, int num){
    int x = ps[i].first, y = ps[i].second;
    for(int i = 1; i <= 2; i++){
        R[x+i][y] = R[x+i][y+4] = '|';
    }
    for(int i = 1; i <= 3; i += 2){
        R[x][y+i] = R[x+2][y+i] = '_';
    }
    for(int j = 1; j <= 3; j++){
        R[x+1][y+j] = ' ';
        if(R[x+2][y+j] == '|') R[x+2][y+j] = ' ';
    }
    if(num == ns){
        int ok = 1;
        for(int i = 0; i < m && ok; i++){
            for(int j = 0; j < n && ok; j++){
                if(G[i][j] != R[i][j]) ok = 0;
            }
        }
        return ok;
    }

    for(int i = 0; i < ns; i++){
        if(!vis[i]){
            vis[i] = 1;
            if(DFS(i, num + 1)) return 1;
            vis[i] = 0;
        }
    }
    return 0;
}

int main()
{
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    int T = 0;
    while(fgets(G[0], 15, stdin) && G[0][0] != '0'){
        for(int i = 1; i < m; i++){
            fgets(G[i], 15, stdin);
        }
        memset(found, 0, sizeof(found));
        ns = count();
        // printf("
ns: %d
", ns);
        ok = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                R[i][j] = ' ';
            }
            R[i][n] = 0;
        }
        if(ns >= 1 && ns <= 6){
            for(int i = 0; i < ns; i++){
                vis[i] = 1;
                if(DFS(i, 1)){ ok = 1; break; }
                vis[i] = 0;
            }
        }
        printf("Case %d: %s
", ++T, ok ? "Yes" : "No");
    }
    return 0;
}