1 条题解

  • 0
    @ 2026-1-31 22:36:00
    #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
    上传者