hdu1728--------坑爹啊

尼瑪，就因為沒發現‘yes’寫成‘yrs’。整整讓哥找了一個小時的bug。有沒有..........此刻，內流滿面！

?

分析：

開始以為是單純的BFS,結果WA無數次！！

后來分析后發現是要找到不超過轉向次數的轉向路徑,

最重要的是已經訪問的節點不能直接標記為已經訪問。因為存在遠距離但是轉向少的情況,所以要標記上每一個已經訪問的點到起點所需要的轉彎次數。

#include<cstdio>??????????????? //這題和連連看一樣，走過的點可以再次訪問
#include<queue>
#include<cstring>
using namespace std;
#define inf 1000000

int result;???????????????????? //初始化為0，結果能走到就為1
char map[105][105];
int visit[105][105];???????????? //初始化為inf ，visit[i][j] 記錄走過該點是的最小轉彎次數
int fang[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int? n,m;
struct node
{
?int x;
?int y;
?int d;??????? //記錄當前該點的方向
?int num;
};

?

void bfs(int k,int x1,int y1,int x2,int y2)
{
?queue<node> qu;
?int i,j;
?node t,tt;
?t.x=x1;
?t.y=y1;
?t.d=-1;
?t.num=0;
?visit[x1][y1]=0;
?qu.push(t);
?
?while(!qu.empty())
?{
??t=qu.front();
??qu.pop();
??if(t.x==x2&&t.y==y2&&t.num<=k)
??{
???result=1;
???return ;
??}
??
??for(i=0;i<4;i++)
??{
???tt.x=t.x+fang[i][0];
???tt.y=t.y+fang[i][1];
???
???if(t.d==-1)
???tt.num=0;
???else if(t.d!=i)
???tt.num=t.num+1;
???else
???tt.num=t.num;
???
???tt.d=i;
???if(tt.x<1||tt.y<1||tt.x>m||tt.y>n)
???continue;
???if(map[tt.x][tt.y]=='.'&&tt.num<=visit[tt.x][tt.y])
???{
????visit[tt.x][tt.y]=tt.num;
????qu.push(tt);
???}
??}
?}
}

int main()
{
?int i,j;
?int t;
?int k,x1,y1,x2,y2;
?scanf("%d",&t);
?while(t--)
?{
??scanf("%d%d",&m,&n);???????????????? //m行，n列
??getchar();
??for(i=1;i<=m;i++)
??{
???for(j=1;j<=n;j++)
???{
????scanf("%c",&map[i][j]);
????visit[i][j]=inf;
???}
???getchar();
??}
??scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
??
??result=0;
??bfs(k,x1,y1,x2,y2);
??if(result==1)
??printf("yes\n");
??else
??printf("no\n");
?}
?return 0;
}

?