Description

wyy是一個著名動畫《境界的彼方》的男主，此時他非常的慌張，因為女主栗山未來進入了境界的彼方內部，并且花費了大量的血量去拯救wyy，wyy此時也進入了境界的彼方，他媽給了他一張地圖去尋找境界的彼方的核心去拯救女主，現給你一張n×n的地圖，以及男主的位置，問男主要拐彎幾次才會到達境界的彼方內部（境界的彼方的位置為(n,n)）
不過你以為這就是道搜索題？還得加條件：此時女主血條狂掉，你必須判斷此時wyy是否可以走到終點且女主的血條不會掉光，如果掉光了那么輸出"Die",如果地圖無法到達境界的彼方（他媽坑他）就輸出"No",如果到得了終點且女主血條活著輸出res代表男主此時要拐彎幾次

Input

給出n和k和x1和y1，k代表每拐彎一次女主要耗掉k滴血， 默認女主有100點血, x1和y1代表男主此時所在的位置

Output

根據題目要求輸出

Samples

Input

3 3 1 1 110 010 011

Output
2
Input

3 50 1 1 110 010 011

Output
Die

Hint

1表示能走，0表示不能走；血量大于0時表示活著。

Source

石光中學 wyy套題 dfs bfs 深搜 廣搜

當時比賽的時候由于種種原因咕咕咕了
現在補了一手

這道題目是比較板子的廣搜題
在后面的博客中可能會總結到更多的相應的題目
代碼可以更短，為了好理解沒有進行處理，更方便理解一些

下面是基本的思路：
為什么要選擇BFS ?
因為BFS的一個節點只能是從某一個節點轉移過來，并不是從多個點轉移過來的（加了vis數組）
而DFS的某一個節點就可能是從若干個節點轉移過來的。
而這個題的背景來看，要輸出轉彎的次數，所以說就要首先有一個唯一的前驅節點轉移得到，所以說BFS的優勢顯而易見，就要用到BFS
在寫BFS的時候，我喜歡用cur表示當前的節點用next表示下一個節點，每當訪問一個節點之后就將這個節點標記為1（vis數組）
對于開始點的位置，我們很巧妙的將開始的血量當成一個值放進結構體中，并且在搜索的過程中進行傳遞變化 （此處來源：大佬）在傳遞的過程中通過在四個方向的判斷中加入轉彎次數的變化，從而在最后進行輸出（判斷當前的方向和下一個的方向是否相同即可）

Main_code()

/*** keep hungry and calm PushyTao!***/ int n,m; int stx,sty; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int a[1007][1007]; int vis[1007][1007]; struct node{int x;int y;int blood; ///start with 100int op;/// the operationint cnt; }; bool edge(int x,int y){if(x>=1&&x<=n&&y>=1&&y<=n)return true;else return false; }void bfs(int x,int y){queue<node> que;node cur,next;cur.x = x;cur.y = y;cur.blood = 100;cur.op = -1;cur.cnt = 0;que.push(cur);int flag = 0;while(que.size() > 0){cur = que.front();que.pop();/// judge if get the edx and edyif(cur.x == n && cur.y == n){if(cur.blood < 0){puts("Die");}else{cout<<cur.cnt - 1<<endl;}flag = 1;break;}for(int i=0;i<4;i++){next.x = cur.x + dx[i];next.y = cur.y + dy[i];if(!edge(next.x,next.y)) continue;if(vis[next.x][next.y]) continue;if(a[next.x][next.y] == 0) continue;vis[next.x][next.y] = 1;int op = cur.op;if(i == 2 || i == 3){next.blood = cur.blood - m;next.op = i;if(op == 2 || op == 3) {next.cnt = cur.cnt;que.push(next);}else{next.cnt = cur.cnt + 1;que.push(next);}}else {next.blood = cur.blood - m;next.op = i;if(op == 1 || op == 0){next.cnt = cur.cnt;que.push(next);}else{next.cnt = cur.cnt + 1;que.push(next);}}}}if(flag == 0) puts("No");} int main() {n=read,m=read;/// n*n - m / stepstx=read,sty=read;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%1d",&a[i][j]);}}if(stx == n && sty == n){puts("0");return 0;}bfs(stx,sty);return 0; } /****/

總結

以上是生活随笔為你收集整理的境界的彼方_lduoj_bfs宽搜的全部內容，希望文章能夠幫你解決所遇到的問題。

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