# 137. 消息传输

这道题目，普通广搜就可以解决。

这里说一下几点注意事项：

1、题目描述中，注意 n 是列数，m是行数

这是造成很多录友周赛的时候提交返回【运行错误】的罪魁祸首，如果输入用例是正方形，那没问题，如果后台输入用例是矩形， n 和 m 搞反了，就会数组越界。

矩阵是 m * n ，但输入的顺序却是先输入n 再输入 m。

这会让很多人把矩阵的 n 和 m 搞反。

其实规范出题，就应该是n 行，m列，然后先输入n，在输入m。

只能说大厂出题的人，也不是专业出题的，所以会在非算法方面一不小心留下很多 “bug”，消耗大家的精力。

2、再写广搜的时候，可能担心会无限循环

即 A 走到 B，B又走到A，A又走到B ，这种情况，一般来说广搜都是用一个 visit数组来标记的。

但本题不用，因为不会重复走的，题图里的信号都是正数，根据距离判断大小可以保证不走回头路。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1e6;
int main () {
    int n, m, startx, starty;
    cin >> n >> m;
    cin >> startx >> starty;
    vector<vector<int>> grid(m, vector<int>(n));
    vector<vector<int>> dis(m, vector<int>(n, inf));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    queue<pair<int, int>> que;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
    que.push(pair<int, int>(startx, starty));
    dis[startx][starty] = 0;
    while(!que.empty()) {
        pair<int, int> cur = que.front(); que.pop();
        for (int i = 0; i < 4; i++)  {
            int newx = cur.first + dir[i][1];
            int newy = cur.second + dir[i][0];
            if (newx < 0 || newx >= m || newy < 0 || newy >= n || grid[cur.first][cur.second] == 0) continue;

            if (dis[newx][newy] > dis[cur.first][cur.second] + grid[cur.first][cur.second]) {
                dis[newx][newy] = dis[cur.first][cur.second] + grid[cur.first][cur.second];
                que.push(pair<int, int>(newx, newy));
            }
        }
    }
    int result = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dis[i][j] == inf) {
                cout << -1 << endl;
                return 0;
            }
            result = max(result, dis[i][j]);
        }
    }
    cout << result << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 其他语言版本

# Java

import java.util.*;

public class Main {
    static final int INF = 1000000;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int startX = scanner.nextInt();
        int startY = scanner.nextInt();

        int[][] grid = new int[m][n];
        int[][] dis = new int[m][n];

        for (int i = 0; i < m; i++) {
            Arrays.fill(dis[i], INF);
            for (int j = 0; j < n; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

        queue.add(new int[]{startX, startY});
        dis[startX][startY] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int[] dir : directions) {
                int newX = current[0] + dir[0];
                int newY = current[1] + dir[1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[current[0]][current[1]] != 0) {
                    if (dis[newX][newY] > dis[current[0]][current[1]] + grid[current[0]][current[1]]) {
                        dis[newX][newY] = dis[current[0]][current[1]] + grid[current[0]][current[1]];
                        queue.add(new int[]{newX, newY});
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][j] == INF) {
                    System.out.println(-1);
                    return;
                }
                result = Math.max(result, dis[i][j]);
            }
        }

        System.out.println(result);
        scanner.close();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# Python

from collections import deque

inf = 1000000

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    index = 0

    n = int(data[index])
    m = int(data[index+1])
    startx = int(data[index+2])
    starty = int(data[index+3])
    index += 4

    grid = []
    dis = [[inf] * n for _ in range(m)]

    for i in range(m):
        grid.append([int(data[index+j]) for j in range(n)])
        index += n

    directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    queue = deque()
    queue.append((startx, starty))
    dis[startx][starty] = 0

    while queue:
        curx, cury = queue.popleft()
        for dx, dy in directions:
            newx, newy = curx + dx, cury + dy
            if 0 <= newx < m and 0 <= newy < n and grid[curx][cury] != 0:
                if dis[newx][newy] > dis[curx][cury] + grid[curx][cury]:
                    dis[newx][newy] = dis[curx][cury] + grid[curx][cury]
                    queue.append((newx, newy))

    result = 0
    for i in range(m):
        for j in range(n):
            if dis[i][j] == inf:
                print(-1)
                return
            result = max(result, dis[i][j])

    print(result)

if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51