杂题——夺宝大赛

L3-1：夺宝大赛

夺宝大赛的地图是一个由 n×m 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。
假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。

输入格式：

输入首先在第一行给出两个正整数 m 和 n（2<m,n≤100），随后 m 行，每行给出 n 个数字，表示地图上对应方格的状态：1 表示方格可通过；0 表示该方格有障碍物，不可通行；2 表示该方格是大本营。题目保证只有 1 个大本营。
接下来是参赛队伍信息。首先在一行中给出正整数 k（0<k<m×n/2），随后 k 行，第 i（1≤i≤k）行给出编号为 i 的参赛队的初始落脚点的坐标，格式为 x y。这里规定地图左上角坐标为 1 1，右下角坐标为 n m，其中 n 为列数，m 为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。

输出格式：

在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出 No winner.

输入样例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4

输出样例 1：

1
7 6

样例 1 说明：

七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。

输入样例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5

输出样例 2：

1
No winner.

思路（多源BFS）

​ 思路一：就是每给一个起点就走一次，搜索一次记录到达目的地的最短距离，同时记录一下每只队伍到达大本营的最短距离和对应的队伍编号，最后只需要排个序然后根据题目的意思判断一下即可得出答案来。但是这样的写法会超时，18/30.

​ 思路二：其实就是稍微优化一点点，我们可以选择从终点出发，算出终点到各个位置的最小距离，最后我们在枚举起点的时候直接赋值即可。这样就可以AC了。

代码一

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
const int N = 110;
int n, m;
int a[N][N];
pair<int, int> p[N];
int xx, yy;
int vis[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

bool cmp(pair<int, int> A,pair<int, int> B){
    return A.first < B.first;
}

int dfs(int x,int y){
    memset(vis, -1, sizeof vis);
    queue<pair<int, int>> q;
    vis[x][y] = 0;
    q.push({x, y});
    while (q.size()){
        auto t = q.front();
        q.pop();
        
        int x1 = t.first;
        int y1 = t.second;
        // cout << x1 << " " << y1 << '\n'
        if (x1 == xx && y1 == yy) {
            return vis[xx][yy];
        }
        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];
            if (x2 >= 1 && x2 <= m && y2 >= 1 && y2 <= n && vis[x2][y2] == -1 && a[x2][y2] == 1) {
                vis[x2][y2] = vis[x1][y1] + 1;
                q.push({x2, y2});
            }
            // cout << x2 << " " << y2 << '\n';
        }
    }
    return vis[xx][yy];
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 2) {
                xx = i;
                yy = j;
                a[i][j] = 1;
            }
        }
    }
    
    int k;
    cin >> k;
    for (int i = 1; i <= k; i++){
        int x, y;
        cin >> x >> y;
        p[i].first = dfs(y, x);
        p[i].second = i;
    }

    sort (p + 1, p + k + 1, cmp);
    
    // for (int i = 1; i < k; i++){
    //     cout << p[i].first << " " << p[i].second << '\n';
    // }
    bool flag = false;
    for (int i = 1; i < k; i++){
        int x = p[i].first, y = p[i].second;
        if (x == p[i + 1].first || (x == p[i - 1].first && i != 1) || x == -1) continue;
        else {
            cout << y << " " << x;
            return 0;
        }
    }
    
    cout << "no winner";
    return 0;
    
}

代码二（优化）

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
const int N = 210, M = 4010;
int n, m;
int a[N][N];
pair<int, int> p[M];
int xx, yy;
int vis[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

bool cmp(pair<int, int> A,pair<int, int> B){
    return A.first < B.first;
}

void bfs(int x,int y){
    memset(vis, -1, sizeof vis);
    queue<pair<int, int>> q;
    vis[x][y] = 0;
    q.push({x, y});
    while (q.size()){
        auto t = q.front();
        q.pop();

        int x1 = t.first;
        int y1 = t.second;
        // cout << x1 << " " << y1 << '\n'
        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];
            if (x2 >= 1 && x2 <= m && y2 >= 1 && y2 <= n && vis[x2][y2] == -1 && a[x2][y2] == 1) {
                vis[x2][y2] = vis[x1][y1] + 1;
                q.push({x2, y2});
            }
            // cout << x2 << " " << y2 << '\n';
        }
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 2) {
                xx = i;
                yy = j;
                a[i][j] = 1;
            }
        }
    }

    bfs(xx, yy);

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++){
        int x, y;
        cin >> x >> y;
        p[i].first = vis[y][x];
        p[i].second = i;
    }

    sort (p + 1, p + k + 1, cmp);

    // for (int i = 1; i < k; i++){
    //     cout << p[i].first << " " << p[i].second << '\n';
    // }
    bool flag = false;
    for (int i = 1; i < k; i++){
        int x = p[i].first, y = p[i].second;
        if (x == p[i + 1].first || (x == p[i - 1].first && i != 1) || x == -1) continue;
        else {
            cout << y << " " << x;
            return 0;
        }
    }

    cout << "No winner.\n";
    return 0;

}