题目描述
小明某天不小心进入了一个迷宫(如上图所示),请帮他判断能否出走出迷宫。每次走只能是上、下、左、右4个方向之一。
输入格式:
测试数据有多组,处理到文件尾。每组测试数据首先输入2个整数n,m(0<n,m≤100),代表迷宫的高和宽,然后n行,每行m个字符,各字符的含义如下:
S 代表小明现在所在的位置;T 代表迷宫的出口;# 代表墙,不能走;. 代表路,可以走。
输出格式:
对于每组测试,若能成功脱险,输出YES,否则输出NO。
输入样例:
4 4
S…
..
..#.
…T
4 4
S…
..
..#.
..#T
输出样例:
YES
NO
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
样例
4 4
S...
#..#
..#.
...T
4 4
S...
#..#
..#.
..#T
YES
NO
算法1
(深搜) $O(nm)$
又是深搜模板题
时间复杂度
$O(nm)$
参考文献
无
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,sx,sy,ex,ey,Min;
char ditu[105][105];
bool used[105][105];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
void dfs(int x,int y,int s)
{
if (x==ex&&y==ey)
Min=min(Min,s);
else
{
for (int i=1;i<=4;i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx<1 || nx>n || ny<1 || ny>m)
continue;
if (ditu[nx][ny]!='#' && used[nx][ny]!=1)
{
used[nx][ny] = 1;
dfs(nx,ny,s+1);
used[nx][ny] = 0;
}
}
}
}
int main()
{
while(cin>>n>>m)
{
Min=INT_MAX;
memset(used,0,sizeof used);
cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ditu[i][j];
if(ditu[i][j]=='S') sx=i,sy=j;
if(ditu[i][j]=='T') ex=i,ey=j;
}
used[sx][sy]=1;
dfs(sx,sy,0);
if(Min==INT_MAX) cout<<"NO\n";
else cout<<"YES"<<"\n";
}
}
而且还是纯宽搜,连SPFA,DJstalk,priority_queue[HTML_REMOVED] ,vector[HTML_REMOVED] > greater[HTML_REMOVED] > > 这样简单的优化都不加
Orz,给哥们看笑了
你加了能怎么样
???
Orz, 从O(nm)成O(nm-1),6
我又不是不会
SPFA=最短路径
看样子没啥实力啊
让我觉得你刚学宽搜
这题太水了
这叫深搜