https://www.jisuanke.com/problem/T1596迷宫(二)dfs
作者:
4733
,
2023-01-17 22:20:47
,
所有人可见
,
阅读 210
注意条件,初始化的乱七八糟,要加为棋盘内(限制范围)
#include <iostream>
char a[100][100];
int v[100][100];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int minn=99999999;
int x1,y1;
int x2,y2;
int n,m;
using namespace std;
void dfs(int x,int y,int step)
{
if(step>=minn)
{
return;
}
if(x==x2&&y==y2)
{
if(step<minn)
{
minn=step;
return;
}
}
for(int k=0;k<=3;k++)
{
int tx,ty;
tx=x+dx[k];
ty=y+dy[k];
if((a[tx][ty]=='.'||a[tx][ty]=='T')&&tx>=1&&tx<=n&&ty>=1&&ty<=m&&v[tx][ty]==1)
{
v[tx][ty]=0;
dfs(tx,ty,step+1);
v[tx][ty]=1;
}
}
}
int main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
v[i][j]=1;
if(a[i][j]=='S')
{
x1=i;
y1=j;
}
if(a[i][j]=='T')
{
x2=i;
y2=j;
}
}
}
v[x1][y1]=0;
dfs(x1,y1,0);
if(minn!=99999999)
{
cout<<minn<<endl;
}
else
{
cout<<-1<<endl;
}
return 0;
}