求思路,不用帮改正;这个他标签明明写是深搜啊,这样为啥会超时?
两组数据都过了,求一些节省时间的办法;
#include<bits/stdc++.h>
using namespace std;
char c;
int xb,yb,xe,ye,a[11][11];
int f=0,anss=-1;
int xx[5]={0,-1,1,0,0},yy[5]={0,0,0,-1,1};
void dfs(int x,int y,int step)
{
if(x==xe&&y==ye)
{
anss=max(step,anss);
f=1;
}
for(int i=1;i<=4;i++)
{
int xxx=x+xx[i];
int yyy=y+yy[i];
if(a[xxx][yyy])
{
a[x][y]=0;
dfs(xxx,yyy,step+1);
a[x][y]=1;
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c;
if(c=='*') a[i][j]=0;
else a[i][j]=1;
if(c=='S')
{
xb=i;
yb=j;
}
if(c=='T')
{
xe=i;
ye=j;
}
}
}
dfs(xb,yb,0);
if(!f) cout<<"-1";
else cout<<anss;
}
#include<iostream>
using namespace std;
struct muban
{
int x;
int y;
int step;
}stu[8000];
char imap[15][15];
int book[15][15];
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
int n,m;
cin>>n>>m;
int stax,stay,endx,endy;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>imap[i][j];
if(imap[i][j]=='S')
{
stax=i;
stay=j;
}
if(imap[i][j]=='T')
{
endx=i;
endy=j;
imap[i][j]='.';
}
}
}
int head,tail;
int tx,ty;
head=1;
stu[head].x=stax;
stu[head].y=stay;
stu[head].step=0;
book[stax][stay]=1;
tail=2;
int stepmin=200;
while(head<tail)
{
for(int i=0;i<4;i++)
{
tx=stu[head].x+next[i][0];
ty=stu[head].y+next[i][1];
if(tx>=0&&tx<n&&ty>=0&&ty<m)
{
if(book[tx][ty]==0&&imap[tx][ty]=='.')
{
stu[tail].x=tx;
stu[tail].y=ty;
stu[tail].step=stu[head].step+1;
book[tx][ty]=1;
tail++;
}
}
if(stu[tail-1].x==endx&&stu[tail-1].y==endy)
{
if(stu[tail-1].step<stepmin)
{
stepmin=stu[tail-1].step;
}
}
}
head++;
}
if(stepmin==200)
cout<<"-1\n"<<endl;
else
cout<<stepmin;
return 0;
}
这里判断一下xxx和yyy的取值范围应该会少走几步,并且如果在这里f已经等于1了,且step大于等于anss可以不用往下走了