1 条题解
-
0
#include <iostream> #include <queue> #include <cstring> #include <climits> using namespace std; #define MAX 55 char g[MAX][MAX]; int n, m; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; // 标记岛屿 void markIsland(int x, int y, char mark) { queue<pair<int, int>> q; q.push({x, y}); g[x][y] = mark; while (!q.empty()) { int cx = q.front().first; int cy = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 'X') { g[nx][ny] = mark; q.push({nx, ny}); } } } } // 计算两个岛屿之间的最短距离 int findShortestPath() { // dist数组记录从第一个岛屿到每个位置的距离 int dist[MAX][MAX]; memset(dist, -1, sizeof(dist)); queue<pair<int, int>> q; // 将所有第一个岛屿的点加入队列 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (g[i][j] == 'A') { dist[i][j] = 0; q.push({i, j}); } } } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); // 如果到达第二个岛屿,返回距离-1(因为最后一个格子是陆地,不需要填充) if (g[x][y] == 'B') { return dist[x][y] - 1; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) { // 可以走海水或者第二个岛屿 if (g[nx][ny] == '.' || g[nx][ny] == 'B') { dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } } } return INT_MAX; // 理论上不会执行到这里 } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> g[i]; } // 标记第一个岛屿为'A' bool foundFirst = false; for (int i = 0; i < n && !foundFirst; i++) { for (int j = 0; j < m && !foundFirst; j++) { if (g[i][j] == 'X') { markIsland(i, j, 'A'); foundFirst = true; } } } // 标记第二个岛屿为'B' bool foundSecond = false; for (int i = 0; i < n && !foundSecond; i++) { for (int j = 0; j < m && !foundSecond; j++) { if (g[i][j] == 'X') { markIsland(i, j, 'B'); foundSecond = true; } } } int result = findShortestPath(); cout << result << endl; return 0; }
- 1
信息
- ID
- 1297
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者