鏈接

[https://vjudge.net/contest/256476#problem/D]

題意

　給定一個m × n (m行, n列)的迷宮，迷宮中有兩個位置，gloria想從迷宮的一個位置走到另外一個位置，當然迷宮中有些地方是空地，gloria可以穿越，有些地方是障礙，她必須繞行，從迷宮的一個位置，只能走到與它相鄰的4個位置中,當然在行走過程中，gloria不能走到迷宮外面去。令人頭痛的是，gloria是個沒什么方向感的人，因此，她在行走過程中，不能轉太多彎了，否則她會暈倒的。我們假定給定的兩個位置都是空地，初始時，gloria所面向的方向未定，她可以選擇4個方向的任何一個出發，而不算成一次轉彎。gloria能從一個位置走到另外一個位置嗎？
Input
　　第1行為一個整數t (1 ≤ t ≤ 100),表示測試數據的個數，接下來為t組測試數據，每組測試數據中，
　　第1行為兩個整數m, n (1 ≤ m, n ≤ 100),分別表示迷宮的行數和列數，接下來m行，每行包括n個字符，其中字符'.'表示該位置為空地，字符'*'表示該位置為障礙，輸入數據中只有這兩種字符，每組測試數據的最后一行為5個整數k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x 1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能轉的彎數，(x 1, y 1), (x 2, y 2)表示兩個位置，其中x 1，x 2對應列，y 1, y 2對應行。
Output
　　每組測試數據對應為一行，若gloria能從一個位置走到另外一個位置，輸出“yes”，否則輸出“no”。
Sample Input
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes

分析

首先題目輸入故意坑人。注意點
因為有轉彎限制，你這時候就得貪心了
就是dfs是就盡快能的往同一方向走這就盡可能地減少轉彎
但是代碼實現的時候有個bug.我后面也是看了別人的才知道自己的錯
[https://www.cnblogs.com/qiufeihai/archive/2012/08/27/2659159.html]
講的很清楚了。需要解釋一下關鍵代碼

str ok;ok.curk=tem.curk+1;for(int i=0;i<4;i++){ok.r=tem.r+d[i][0],ok.c=tem.c+d[i][1];while(ok.r>=1&&ok.r<=n&&ok.c>=1&&ok.c<=m&&ma[ok.r][ok.c]=='.'){//即使其他方向的走過了這里，但是從另一個方向走的時候是可以經過這個位置的 if(!vis[ok.r][ok.c]){//沒檢測過的點就檢測 q.push(ok);vis[ok.r][ok.c]=1;}//即使檢測過了我也可以經過這個點往其他方向搜索 ok.r+=d[i][0];ok.c+=d[i][1];}}

完整代碼

#include<iostream> #include<string.h> #include<queue> #include<algorithm> #include<cstdio> using namespace std; const int N=110; char ma[N][N]; bool vis[N][N]; int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //上下左右 int x1,x2,y1,y2,k,n,m; bool flag; struct str{int r,c,curk; }; void bfs(){str tem;memset(vis,0,sizeof(vis));tem.r=x1,tem.c=y1,tem.curk=-1;vis[x1][y1]=1;queue<str> q;q.push(tem);while(!q.empty()){tem=q.front();q.pop();if(tem.r==x2&&tem.c==y2&&tem.curk<=k){flag=1; break;}str ok;ok.curk=tem.curk+1;for(int i=0;i<4;i++){ok.r=tem.r+d[i][0],ok.c=tem.c+d[i][1];while(ok.r>=1&&ok.r<=n&&ok.c>=1&&ok.c<=m&&ma[ok.r][ok.c]=='.'){//即使其他方向的走過了這里，但是從另一個方向走的時候是可以經過這個位置的 if(!vis[ok.r][ok.c]){//沒檢測過的點就檢測 q.push(ok);vis[ok.r][ok.c]=1;}//即使檢測過了我也可以經過這個點往其他方向搜索 ok.r+=d[i][0];ok.c+=d[i][1];}}} } int main(){int t;//freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){memset(vis,0,sizeof(vis));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ma[i][j];scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);flag=0;bfs();if(flag)printf("yes\n");else printf("no\n");}return 0; }

轉載于:https://www.cnblogs.com/mch5201314/p/10645351.html

總結

以上是生活随笔為你收集整理的hdu-1728(贪心bfs的灵活运用吧)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。