这题开始时以为是简单的搜索题，错了好几次，上网上参考了一下，才恍然大悟，搜一个方向要一直搜到底，或者让一些点重新入队，实现再次搜索，这样写完后还是wa，又重新看了一下代码，写错了一个字符。
参考代码：
#include<stdio.h>
#include<queue>
using namespace std;
int n,m,k;
char s[105][105];
int vis[105][105],dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
struct zhang
{
int x,y,bu,d;
};
bool diy(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='.')
return true ;
else return false ;
}
void bfs(int x1,int y1)
{
int i;
queue<zhang>q;
zhang current,next;
for(i=0;i<4;i++)
{
current.x=x1+dx[i];
current.y=y1+dy[i];
current.bu=0;
current.d=i;
if(diy(current.x,current.y))
{
vis[current.x][current.y]=0;
q.push(current);
}
}
while(!q.empty())
{
current=q.front();
q.pop();
for(i=0;i<4;i++)
{
next.x=current.x+dx[i];
next.y=current.y+dy[i];
if(current.d!=i)
next.bu=current.bu+1;
else next.bu=current.bu;
next.d=i;
if(next.bu<=k&&diy(next.x,next.y))
{
if(next.bu<=vis[next.x][next.y])//很重要！如果步数相等则再次入队，
{ //等于又在另一个方向上进行
vis[next.x][next.y]=next.bu;
q.push(next);
}
}
}
}
}
int main()
{
int T,i,y1,x1,x2,y2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%s",s[i]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
y1--;x1--;y2--;x2--;
for(i=0;i<n;i++)
for(int j=0;j<m;j++)
vis[i][j]=20;
bfs(x1,y1);
if(vis[x2][y2]<=k)
printf("yes\n");
else printf("no\n");
}
return 0 ;
}
源代码：
#include<stdio.h>
#include<queue>
using namespace std;
int vis[150][150];
char s[150][150];
int n,m,k,y2,x2;
struct zhang
{
int x,y,bu,d;
};
void bfs(int x1,int y1)
{
int i;
zhang current,next;
queue<zhang>q;
current.x=x1;
current.y=y1;
current.bu=0;
current.d=-1;
vis[current.x][current.y]=-1;
q.push(current);
while(!q.empty())
{
current=q.front();
q.pop();
if(current.d==-1)//刚开始搜索时
{
for(i=current.y+1;i<m;i++)//右 1
if(s[current.x][i]!='*')
{
next.d=1;
next.x=current.x;
next.y=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.y-1;i>=0;i--)// 左 2
if(s[current.x][i]!='*')
{
next.d=2;
next.x=current.x;
next.y=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.x-1;i>=0;i--)// 上 3
if(s[i][current.y]!='*')
{
next.d=3;
next.y=current.y;
next.x=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
for(i=current.y+1;i<n;i++)// 下 4
if(s[i][current.y]!='*')
{
next.d=4;
next.y=current.y;
next.x=i;
next.bu=0;
vis[next.x][next.y]=0;
q.push(next);
}
else break;
}
else {//沿着四个方向一直搜到底
for(i=current.y+1;i<m;i++)// 右 1
if(s[current.x][i]!='*')
{
if(current.d!=1)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[current.x][i])
{
vis[current.x][i]=next.bu;
next.d=1;
next.x=current.x;
next.y=i;
q.push(next);
}
}
else break;
for(i=current.y-1;i>=0;i--)// 左 2
if(s[current.x][i]!='*')
{
if(current.d!=2)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[current.x][i])
{
vis[current.x][i]=next.bu;
next.d=2;
next.x=current.x;
next.y=i;
q.push(next);
}
}
else break;
for(i=current.x-1;i>=0;i--)// 上 3
if(s[i][current.y]!='*')
{
if(current.d!=3)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[i][current.y])
{
vis[i][current.y]=next.bu;
next.d=3;
next.x=i;
next.y=current.y;
q.push(next);
}
}
else break;
for(i=current.x+1;i<n;i++)// 下 4
if(s[i][current.y]!='*')
{
if(current.d!=4)
next.bu=current.bu+1;
else
next.bu=current.bu;
if(next.bu<vis[i][current.y])
{
vis[i][current.y]=next.bu;
next.d=4;
next.x=i;
next.y=current.y;
q.push(next);
}
}
else break;
}
}
}
int main()
{
int T,x1,y1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",s[i]);
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
y2--; x2--;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
vis[i][j]=20;
bfs(x1-1,y1-1);
if(vis[x2][y2]<=k)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
//必须全部搜完有一些点的拐弯次数不断在更新