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;
}
/**
**/
