데이터 구조의 스 택 과 대기 열 - 미로 로 가기 (dfs 깊이 검색)

미로 에 빠지다
Time Limit: 1000MS Memory limit: 65536K
제목 설명
n * m 칸 으로 구 성 된 미로 입 니 다. 출발점 은 (1, 1) 이 고 종점 은 (n, m) 입 니 다. 매번 상하 좌우 네 방향 으로 한 걸음 씩 마음대로 걸 을 수 있 습 니 다. 그리고 어떤 칸 은 걸 을 수 없습니다. 출발점 에서 종점 까지 모든 칸 에서 한 번 이상 걸 을 수 있 는 방법 을 구 합 니 다.
입력
       첫 줄 의 정수 T 는 T 조 테스트 데이터 가 있 음 을 나타 낸다.(T <= 110)
각 그룹의 테스트 데이터:
첫 번 째 줄 의 정수 n, m 는 미로 에 n * m 칸 이 있다 는 것 을 나타 낸다.(1 < = n, m < = 6, (n, m)! = (1, 1) 다음 n 줄, 줄 당 m 개 수.그 중에서 i 줄 의 j 개 수 는 0 으로 i 줄 의 j 개 칸 이 갈 수 있다 는 것 을 나타 낸다. 그렇지 않 으 면 1 은 이 칸 이 갈 수 없다 는 것 을 나타 내 고 입력 은 출발점 과 종점 이 모두 갈 수 있다 는 것 을 보증한다.
임의의 두 조 의 테스트 데이터 간 에 빈 줄 로 나 뉜 다.
출력
 각 조 의 테스트 데이터 에 대해 하나의 정수 R 을 출력 하면 R 가지 방법 이 있 음 을 나타 낸다.
 
예제 입력

3

2 2

0 1

0 0

2 2

0 1

1 0

2 3

0 0 0

0 0 0

예제 출력

1

0

4

#include <iostream>

#include <string>

#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



unsigned int map[6][6];

bool vis[6][6];

int dir[4][2]={{0, -1}, {0, 1}, {1, 0}, {-1, 0} }; //       



int cnt; //     

int n, m;



void dfs(int x, int y)

{

    int i, j;

    int xx, yy;



    for(i=0; i<4; i++)

    {

        xx=x+dir[i][0];

        yy=y+dir[i][1];  //          



        if( xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]==0 && vis[xx][yy]==false ) //     

        {

            if(xx==n-1 && yy==m-1)

            {

                cnt++;

                continue;

            }

            else

            {

                vis[xx][yy]=true; //      

                dfs(xx, yy); //             dfs

                vis[xx][yy]=false; //     dfs    ，           ，

                                   //                ，       ，

                                   //       

            }

        }

    }

}





int main()

{

    int t;

    cin>>t;

    int i, j;



    while(t--)

    {

        cin>>n>>m;

        cnt=0;

        for(i=0; i<n; i++)

        {

            for(j=0; j<m; j++)

            {

                cin>>map[i][j];

                vis[i][j]=false;

            }

        }

        vis[0][0]=true;

        dfs(0, 0);

        cout<<cnt<<endl;

    }

    return 0;

}