走迷宫

电玩女神 2022-08-18 02:28 18阅读 0赞

## 走迷宫 ##

##### 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 种走法。

## 示例输入 ##

32 20 10 02 20 11 02 30 0 00 0 0

## 示例输出 ##

104

## 提示 ##

## 来源 ##

## 示例程序 ##

#include<stdio.h>    
    #include<string.h>    
        
    int dir[4][4] = {
       {0, -1}, {0, 1}, {-1, 0}, {1, 0}};    
    int n, m, count, visit[10][10], map[10][10];    
        
    void dfs(int r, int c);    
    int main(){    
        int T, i, j;    
        scanf("%d", &T);    
            
        while(T--){    
            scanf("%d %d", &n, &m);    
                
            for(i = 0; i < n; i++){    
                for(j = 0; j < m; j++){    
                    scanf("%d", &map[i][j]);    
                }    
            }    
            memset(visit, 0, sizeof(visit));    
            count = 0;    
                
            dfs(0, 0);    
            printf("%d\n", count);    
        }    
        return 0;    
    }    
        
    void dfs(int r, int c){    
        int i, row, col;    
            
        if(r == n - 1 && c == m - 1){    
            count++;    
            return ;    
        }    
            
        if(r >= 0 && r < n && c >= 0 && c < m && !visit[r][c] && !map[r][c]){    
            visit[r][c] = 1;    
            dfs(r - 1, c);    
            dfs(r + 1, c);    
            dfs(r, c - 1);    
            dfs(r, c + 1);    
            visit[r][c] = 0;    
        }    
    }