该死的杭电。读入的时候竟然先读入纵坐标。。。
开始以为是单纯的BFS,结果WA无数次.后来分析后发现因为是要找到最少转向路径,所以要每个方向搜到尽头.
两个AC代码。。
#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
int map[101][101];
char str[101][101];
int n,m,ex,ey,sx,sy,T,step;
int d[4][2]={{0,1},{-1,0},{1,0},{0,-1}};
struct node
{
int x,y,step,dir;
};
void bfs()
{
memset(map,50,sizeof(map));
queue<node>Q;
node q,p;
int k;
q.x=sx;
q.y=sy;
q.step=0;
q.dir=-1;
map[q.x][q.y]=0;
Q.push(q);
while(!Q.empty())
{
q=Q.front();
Q.pop();
for(k=0;k<4;k++)
{
p=q;
p.x+=d[k][0];
p.y+=d[k][1];
if(p.x>=n||p.x<0||p.y>=m||p.y<0||str[p.x][p.y]=='*')
continue;
if(p.dir!=k&&p.dir!=-1)
p.step++;
if(p.step>step)
continue;
if(p.x==ex&&p.y==ey)
{
printf("yes\n");
return ;
}
if(map[p.x][p.y]>=p.step)
{
p.dir=k;
map[p.x][p.y]=p.step;
Q.push(p);
}
}
}
printf("no\n");
return ;
}
int main()
{
int i;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%s",str[i]);
scanf("%d %d %d %d %d",&step,&sy,&sx,&ey,&ex);
sx--;sy--;ex--;ey--;
if(sx==ex&&sy==ey)
{
printf("yes\n");
continue;
}
else
bfs();
}
return 0;
}#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
struct node
{
int x,y,step;
}s,e;
queue<node>qu;
int d[4][2]={-1,0,0,1,1,0,0,-1};
bool f[110][110];
char map[110][110];
int n,m,bx,by,ex,ey,k;
void init()
{
memset(f,false,sizeof(f));
while(!qu.empty())qu.pop();
memset(map,0,sizeof(map));
}
bool is_ok(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]=='.')
return true;
return false;
}
void bfs()
{
int i,xx,yy;
if(bx==ex&&by==ey)
{
printf("yes\n");
return ;
}
f[bx][by]=true;
s.x=bx;s.y=by;
s.step=-1;
qu.push(s);
while(!qu.empty())
{
s=qu.front();
qu.pop();
for(i=0;i<4;i++)
{
xx=s.x+d[i][0];
yy=s.y+d[i][1];
while(is_ok(xx,yy))
{
if(f[xx][yy]==false)
{
f[xx][yy]=true;
e.x=xx;
e.y=yy;
e.step=s.step+1;
qu.push(e);
if(e.x==ex&&e.y==ey&&e.step<=k)
{
printf("yes\n");
return ;
}
}
xx+=d[i][0];
yy+=d[i][1];
}
}
}
printf("no\n");
return ;
}
int main()
{
int cas,i;
scanf("%d",&cas);
while(cas--)
{
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf(" %c",&map[i][j]);
scanf("%d%d%d%d%d",&k,&by,&bx,&ey,&ex);
bfs();
}
return 0;
}