说起bfs和dfs模板，就是智闯迷宫
http://www.bjfuacm.com/problem/62/
题目：
描述
有一个N*M大小的矩阵迷宫，由字符 ’ . ’ 和 ‘ # ’ 组成。起点位于第一行第一列，终点位于最后一行最后一列。想要机智的闯迷宫当然是走最短路径啦！机智的你来算一算迷宫的最短路径吧！(起点为左上角，重点为右下角)
输入
有多组测试
每组测试第一行输入两个数字N，M（0 < N,M < 20），空格隔开。接下来N行输入N*M大小矩阵。只有字符 ‘ . ’ 和 ‘ # ’ 组成。 ‘ . ’ 表示可以走的路，‘ # ’ 表示高高的障碍物。
输出
每组输出从起点到终点的最短路径长度（保证数据每组都有解）
样例输入1 复制
3 3
…
…
…
样例输出1
4
样例输入2 复制
4 4
….
#.##
….
#.#.
样例输出2
6
##代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
char map[22][22];
int vis[22][22];
int n,m,t=0,l=420;
int to[4][2]={1,0,0,1,-1,0,0,-1};
/*void dfs(int x,int y)
{
int tx,ty;
t++;
for(int i=0;i<4;i++)
{
tx=x+to[i][0];
ty=y+to[i][1];
if(tx<0||ty<0||tx>=n||ty>=m||map[tx][ty]=='#'||vis[tx][ty]==1)
continue;
if(map[tx][ty]=='.'&&vis[tx][ty]==0)
{vis[tx][ty]=1;
if((tx==n-1)&&(ty==m-1)&&t<l)
l=t;
dfs(tx,ty);
}
}
t--;
}*/
struct node
{
int x;
int y;
};
queue<node>que;
void bfs(int x,int y)
{
struct node q;
q.x=x;
q.y=y;
que.push(q);
while(!que.empty())
{
q=que.front();
for(int i=0;i<4;i++)
{
q.x+=to[i][0];
q.y+=to[i][1];
if(q.x<0||q.y<0||q.x>=n||q.y>=m)
{
continue;
}
if(map[q.x][q.y]=='#'||vis[q.x][q.y]==1)
continue;
if(map[q.x][q.y]=='.'&&vis[q.x][q.y]==0)
{que.push(q);
t++;}
if(q.x==n-1&&q.y==m-1)
return ;
}
que.pop();
}
}*/
int main()
{
memset(vis,0,sizeof(vis));
while(cin>>n>>m){
l=420;
t=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>map[i][j];
dfs(0,0);
if(n==1&&m==1)
l=0;
cout<<l<<endl;}
return 0;
}
|
