走迷宫
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.h>
using namespace std;
int visited[][];
int m,n;
int f[][],sum;
int hang[]={,,,-},lie[]={,,-,};
void dfs(int h,int l)
{
visited[h][l]=;
int i;
for(i=;i<=;i++)
{
int h1=h+hang[i];
int l1=l+lie[i];
if(h1>=&&h1<=m&&l1>=&&l1<=n)
{
if(f[h1][l1]==&&visited[h1][l1]!=)
{
if(h1==m&&l1==n)
sum++;
else dfs(h1,l1);
}
}
}
visited[h][l]=;
}
int main()
{
int zong;
cin>>zong;
while(zong--)
{
memset(visited,,sizeof(visited));
memset(f,,sizeof(f));
sum=;
cin>>m>>n;
int i,j;
for(i=;i<=m;i++)
for(j=;j<=n;j++)
cin>>f[i][j];
dfs(,);
cout<<sum<<endl;
}
return ;
}
题目链接：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2449
