BFS入门刷题

目录

P1746 离开中山路

P1443 马的遍历

P1747 好奇怪的游戏

P2385 [USACO07FEB] Bronze Lilypad Pond B

---

P1746 离开中山路

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n;
int startx, starty;
int endx, endy;
char a[1010][1010];
int dis[1010][1010];
queue<pair<int, int>> q;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
int bfs(int x, int y)
{memset(dis, -1, sizeof dis);dis[x][y] = 0;q.push({x, y});while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && a[nx][ny] != '1' && dis[nx][ny] <= 0){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}return dis[endx][endy];
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}cin >> startx >> starty >> endx >> endy;cout << bfs(startx, starty);return 0;
}

P1443 马的遍历

2个样例TLE：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dis[410][410];
int n, m;
queue<pair<int, int>> q;
int startx, starty;
int bfs(int x, int y)
{if (x == startx && y == starty){return 0;}memset(dis, -1, sizeof dis);q.push({startx, starty});dis[startx][starty] = 0;while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 8; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && dis[nx][ny] <= 0){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}return dis[x][y];
}
int main()
{cin >> n >> m >> startx >> starty;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << bfs(i, j) << " ";}cout << endl;}return 0;
}

作者一开始想的是每个点都要计数，所以每个点都要搜一次，然后返回一个值

其实只要搜一次

用void类型，不用返回，从开始搜到结尾，然后每个点都会一层一层地搜到，最后dis数组里存的就是每个点的计数

优化：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dis[410][410];
int n, m;
queue<pair<int, int>> q;
int startx, starty;
void bfs(int x, int y)
{memset(dis, -1, sizeof dis);q.push({startx, starty});dis[startx][starty] = 0;while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 8; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && dis[nx][ny] <= 0){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}
}
int main()
{cin >> n >> m >> startx >> starty;bfs(startx, starty);dis[startx][starty] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << dis[i][j] << " ";}cout << endl;}return 0;
}

调用STL中的queue调用坐标需要花费比较长的时间，我们可以用数组来模拟queue节省时间

再优化：

#include <iostream>
#include <cstring>
using namespace std;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dis[410][410];
int n, m;
pair<int, int> q[410 * 410];
int startx, starty;
void bfs(int x, int y)
{memset(dis, -1, sizeof dis);int head = 0;int tail = 0;q[0] = {x, y};dis[x][y] = 0;while (head <= tail){auto t = q[head++];for (int i = 0; i < 8; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && dis[nx][ny] <= 0){q[++tail] = {nx, ny};dis[nx][ny] = dis[t.first][t.second] + 1;}}}
}
int main()
{cin >> n >> m >> startx >> starty;bfs(startx, starty);dis[startx][starty] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << dis[i][j] << " ";}cout << endl;}return 0;
}

好像看不出什么区别

P1747 好奇怪的游戏

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int x1, y1;
int x2, y2;
int dis[30][30];
queue<pair<int, int>> q;
int dx[] = {1, 2, 2, 1, -1, -2, -2, -1, 2, 2, -2, -2};
int dy[] = {2, 1, -1, -2, -2, -1, 1, 2, 2, -2, -2, 2};
int bfs(int x, int y)
{memset(dis, -1, sizeof dis);q.push({x, y});dis[x][y] = 0;while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 12; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= 20 && ny <= 20 && dis[nx][ny] <= 0){q.push({nx, ny});dis[nx][ny] = dis[t.first][t.second] + 1;}}}return dis[1][1];
}
int main()
{cin >> x1 >> y1 >> x2 >> y2;cout << bfs(x1, y1) << endl;cout << bfs(x2, y2) << endl;return 0;
}

P2385 [USACO07FEB] Bronze Lilypad Pond B

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
queue<pair<int, int>> q;
int m, n;
int m1, n1;
int a[35][35];
int dis[35][35];
int startx, starty, endx, endy;
int bfs(int x, int y)
{memset(dis, -1, sizeof dis);q.push({x, y});dis[x][y] = 0;while (!q.empty()){auto t = q.front();q.pop();int dx[] = {m1, m1, -m1, -m1, n1, n1, -n1, -n1};int dy[] = {n1, -n1, n1, -n1, m1, -m1, m1, -m1};for (int i = 0; i < 8; i++){int nx = t.first + dx[i];int ny = t.second + dy[i];if (nx >= 1 && ny >= 1 && nx <= m && ny <= n && a[nx][ny] != 0 && a[nx][ny] != 2 && dis[nx][ny] == -1){dis[nx][ny] = dis[t.first][t.second] + 1;q.push({nx, ny});}}}return dis[endx][endy];
}
int main()
{cin >> m >> n >> m1 >> n1;for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];if (a[i][j] == 3){startx = i;starty = j;}if (a[i][j] == 4){endx = i;endy = j;}}}cout << bfs(startx, starty);return 0;
}