php网页设计完整代码_阿里巴巴国际站的前台网址是_互联网推广招聘_深圳知名网络优化公司

//输入格式
//输入包含10行，每行10个字符，描述这个农场的布局。输入保证图案中恰有一个字符 B、一个字符 L 以及一个字符 R。
//输出格式
//输出一个整数，为组成一条从B到L的的最短路径（避开R）。
//https://www.luogu.com.cn/problem/P1699
#include<bits/stdc++.h>
using namespace std;
char mp[10][10];
int sx, sy, tx, ty;
bool vis[10][10];
int xx[] = { 1,-1,0,0 };
int yy[] = { 0,0,1,-1 };
struct node {int x, y, step;
};
int bfs(int sx, int sy, int tx, int ty)
{queue<node> qu;qu.push(node{sx,sy,0});while (!qu.empty()){node f = qu.front();qu.pop();for (int i = 0; i < 4; i++){int x = f.x + xx[i];int y = f.y + yy[i];if (vis[x][y]) continue;if (mp[x][y] == 'R') continue;if (x<0 || x>9 || y<0 || y>9) continue;if (x == tx && y == ty){return f.step;}           vis[x][y] = 1;node New;New.x = x;New.y = y;New.step = f.step+1;qu.push(New);   }}return -1;
}int main()
{memset(vis, 0, sizeof vis);for (int i = 0; i < 10; i++){for (int j = 0; j < 10; j++){cin >> mp[i][j];if (mp[i][j] == 'B'){sx = i;sy = j;}if (mp[i][j] == 'L'){tx = i;ty = j;}}}int ret=bfs(sx, sy, tx, ty);cout << ret<< endl;return 0;
}

在涉及最短路径问题时，应该在不断向外遍历时多加一个记录遍历层数的变量（上题用的时step）；如果说DFS是一条在地图上的贪吃蛇，一条道走到黑，直到走不通再return回去直到能走通，那么BFS就是以起点为中心不断向外扩散的水波一层层地向外蔓延。