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 100 int op;/// the operation int 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 edy if(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 / step stx=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; } /** **/
