HDU 1426 DFS

http://acm.hdu.edu.cn/showproblem.php?pid=1426 
Sudoku KillerTime Limit: 2000 / 1000 MS (Java / Others) Memory Limit: 65536 / 32768 K (Java / Others) Total Submission (s): 1647 Accepted Submission (s): 478 Problem 설명 2006 년 3 월 10 일부 터 11 일 까지 제1회 세계 선수권대회 이후 이 게임 은 점점 사람들의 사랑 과 중 시 를 받 고 있다.2008 베 이 징 올림픽 에 서 는 단독 종목 으로 경 기 를 치 를 예정 이 며, 우승 은 커 다란 상품 인 HDU 무료 7 일 여행 에 lcy 친필 서명 과 hdu acm 팀 과 기념 사진 을 찍 을 수 있 는 기회 가 될 것 이 라 고 한다.그래서 전 세계 사람들 이 앞 뒤 를 이 어 상품 을 위해 밤낮으로 차 와 밥 을 훈련 시 켰 다.물론 초보 자 린 도 포함 되 어 있 습 니 다. 하지만 그 는 너무 멍청 하고 인내심 이 별로 없어 서 가장 기본 적 인 문 제 를 풀 수 밖 에 없습니다. 하지만 그 는 여전히 그 상품 을 받 고 싶 습 니 다. 당신 이 그 를 도와 주 시 겠 습 니까?너 는 그 에 게 답 만 알려 주면 돼, 그 에 게 어떻게 하 는 지 가르쳐 줄 필요 없어.게임 의 규칙 은 다음 과 같 습 니 다. 9x9 의 칸 에 숫자 1 - 9 를 빈 칸 에 기입 하고 칸 의 줄 과 열 에 1 - 9 라 는 9 개의 숫자 를 포함 시 켜 야 합 니 다.또한 빈 칸 에 굵 은 선 으로 9 개의 3x3 칸 으로 나 누 는 것 도 1 - 9 라 는 9 개의 숫자 를 동시에 포함 하도록 해 야 한다.예 를 들 어 이런 문제 가 있 으 면 여러분 은 자세히 관찰 할 수 있 습 니 다. 이 안에 각 줄, 각 열, 그리고 각 3x3 의 격자 에는 1 - 9 라 는 9 개의 숫자 가 포함 되 어 있 습 니 다.예제: 정 답: Input 본 문 제 는 여러 조 의 테스트 를 포함 하고 각 조 간 에 빈 줄 로 나 뉜 다.각 조 의 테스트 는 9 * 9 의 행렬 을 줄 것 이 며, 같은 줄 에 인접 한 두 요 소 는 하나의 빈 칸 으로 나 눌 것 이다.그 중 1 - 9 는 이 위치의 이미 기입 한 수 를 대표 하고 물음표 (?) 는 네가 기입 해 야 할 수 를 나타 낸다.Output 은 각 그룹의 테스트 에 대해 해 를 출력 하 십시오. 같은 줄 에 인접 한 두 수 는 하나의 빈 칸 으로 나 누 십시오.두 조 의 해 사 이 는 빈 줄 로 해 야 한다.각 그룹의 테스트 데이터 에 대해 그것 이 있 고 하나만 풀 수 있다 는 것 을 보증한다.Sample Input7 1 2 ? 6 ? 3 5 8? 6 5 2 ? 7 1 ? 4? ? 8 5 1 3 6 7 29 2 4 ? 5 6 ? 3 75 ? 6 ? ? ? 2 4 11 ? 3 7 2 ? 9 ? 5? ? 1 9 7 5 4 8 66 ? 7 8 3 ? 5 1 98 5 9 ? 4 ? ? 2 3 Sample Output7 1 2 4 6 9 3 5 83 6 5 2 8 7 1 9 44 9 8 5 1 3 6 7 29 2 4 1 5 6 8 3 75 7 6 3 9 8 2 4 11 8 3 7 2 4 9 6 52 3 1 9 7 5 4 8 66 4 7 8 3 2 5 1 98 5 9 6 4 1 7 2 3
 
샅 샅 이 뒤 졌 다

#include <iostream>

using namespace std;
int map[10][10];
int count,flag;

struct Node
{
    int x,y;
}q[81];

bool Check(int value,int CurrentNumber)
{
    int i,j;
    int row=q[CurrentNumber].x;
    int col=q[CurrentNumber].y;

    for (j=0;j<9;j++) //     
    {
        if(map[row][j]==value)
            return false;
    }
    for(i=0;i<9;i++) //     
    {
        if(map[i][col]==value)
            return false;
    }

    int rr=(row/3)*3;
    int cc=(col/3)*3;

    // 3*3     
    for (i=rr;i<rr+3;i++)
        for (j=cc;j<cc+3;j++)
        {
            if(map[i][j]==value)
                return false;
        }
    return true;
}

void DFS(int CurrentNumber)
{
    //    
    if(CurrentNumber==count)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<8;j++)
                cout<<map[i][j]<<" ";
            cout<<map[i][8]<<endl;
        }
        flag=1;
        return;
    }
    else
    {
        for (int i=1;i<=9;i++)
        {
            if (Check(i,CurrentNumber)&&!flag)
            {
                //  
                map[q[CurrentNumber].x][q[CurrentNumber].y]=i;
                DFS(CurrentNumber+1);
                //  
                map[q[CurrentNumber].x][q[CurrentNumber].y]=0;
            }
        }
    }
}


int main()
{
    int cas=0;
    char c;
    while(cin>>c)
    {
        count=0;
        if (c=='?')
        {
            map[0][0]=0;
        }
        else
            map[0][0]=c-'0';

        for (int i=0;i<9;i++)
        {
            for (int j=0;j<9;j++)
            {
                if(!(i==0&&j==0))
                    cin>>c;

                if (c=='?')
                {
                    map[i][j]=0;
                    q[count].x=i;
                    q[count].y=j;
                    count++;
                } 
                else
                    map[i][j]=c-'0';
            }
        }
        flag=0;
        if(cas++)
            cout<<endl;

        DFS(0);
    }
    return 0;
}