用bfs做的,代码不是很长
代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
int head=0,tail=1,nextx,nexty,r,c,beginx,beginy,endx,endy;
int pre[100000],a[100000],b[100000];
int x[4]={0,0,1,-1},y[4]={1,-1,0,0},total;
bool mark[200][200],flag;
char map[200][200];
void find(int d)
{
if(pre[d]!=0)find(pre[d]);
total++;
}
bool check(int x,int y)
{
if(x<r&&y<c&&x>=0&&y>=0)return 1;
return 0;
}
void bfs()
{
memset(mark,0,sizeof(mark));
a[1]=beginx;
b[1]=beginy;
mark[beginx][beginy]=1;
pre[1]=0;
head=0;tail=1;
while(head!=tail)
{
head++;
for(int i=0;i<4;i++)
{
nextx=a[head]+x[i];
nexty=b[head]+y[i];
if(check(nextx,nexty)&&!mark[nextx][nexty]&&map[nextx][nexty]!='#')
{
tail++;
a[tail]=nextx;
b[tail]=nexty;
pre[tail]=head;
mark[nextx][nexty]=1;
if(a[tail]==endx&&b[tail]==endy)
{
find(tail);
printf("%d\n",total-1);
flag=1;
return ;
}
}
}
}
}
main()
{
int t;
scanf("%d",&t);
while(t--)
{
flag=0;
total=0;
scanf("%d%d",&r,&c);
for(int i=0;i<r;i++)
{
scanf("%s",map[i]);
for(int j=0;j<c;j++)
{
if(map[i][j]=='S'){beginx=i;beginy=j;}
if(map[i][j]=='E'){endx=i;endy=j;}
}
}
if(beginx==endx&&beginy==endy)
{
printf("0\n");
continue;
}
bfs();
if(!flag) printf("oop!\n");
}
}