6.4 神奇宝贝

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

小\(X\)同学最近玩起了复古的神奇宝贝游戏。游戏地图为一个\(n\times m\)的方格组成，地图中有如下一些表示：

T： 该方格被树木占据，不可穿过；

S： 小\(X\)同学的起始位置，保证图中只包含一个 S；

E： 地图的出口，保证图中只包含一个 E；

0~9： 表示地图该位置存在\(i\)个其它玩家。

游戏规则如下：每次操作所有玩家可以不行动或行动到相邻的可移动方格中。若小\(X\)与其他玩家在同一方格相遇，他就需要与该方格内所有其他玩家分别完成一次决斗。由于小\(X\)在这个服务器很出名，其他玩家都会尽一切可能遇上他并进行决斗。当小\(X\)走到地图出口时结束游戏（若在出口处相遇，仍需进行完决斗后出地图）。小\(X\)想知道他最少需要参加多少次决斗。

数据输入

输入的第一行为包括两个整数\(n\)，\(m\ (1\leq n,m\leq 1000)\)表示地图的大小。接下来\(n\)行，每行\(m\)个字符表示地图，包含字符如题所述。

数据输出

输出一个整数表示小 X 同学在游戏中需要参加的最少决斗次数。

输入示例 输出示例
5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000		 3
1 4
SE23		 2

源代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

#define maxn 1005

class Position{
    int x, y;
public:
    const int getx(){ return x; }
    const int gety(){ return y; }
    Position(int _x, int _y) :x(_x), y(_y){}
    Position() :x(0), y(0){}
    bool operator==(Position t){
        return this->x == t.x&&this->y == t.y;
    }
    Position operator+(Position t){
        return Position(this->x + t.x, this->y + t.y);
    }
};

Position offset[4] = { Position(0, 1), Position(1, 0), Position(0, -1), Position(-1, 0) };

class Map{
    int map[maxn][maxn];
    int num[maxn][maxn];
public:
    Map(){
        memset(map, 0, sizeof(map));
        memset(num, 0, sizeof(num));
    }
    inline bool equal(Position pos, int val){
        return map[pos.getx()][pos.gety()] == val;
    }
    inline void setNum(Position pos, int val){
        num[pos.getx()][pos.gety()] = val;
    }
    inline void setMap(Position pos, int val){
        map[pos.getx()][pos.gety()] = val;
    }
    inline int getMap(Position pos){
        return map[pos.getx()][pos.gety()];
    }
    inline int getNum(Position pos){
        return num[pos.getx()][pos.gety()];
    }
    int findPath(Position start, Position finish){
        //参考教材//if (start == finish){ return 0;}//按题设条件不可能存在这个情况
        Position here = start, nbr;
        setMap(start, 2);
        queue<Position> myqueue;
        myqueue.push(start);
        int maxLen = 0x3f3f3f3f;
        int total = 0;
        int len;
        while (!myqueue.empty()){
            here = myqueue.front();
            myqueue.pop();
            len = getMap(here);
            total += getNum(here);
            if (len >= maxLen)continue;
            for (int i = 0; i < 4; ++i){
                nbr = here + offset[i];
                if (equal(nbr, 0) && len <= maxLen){
                    setMap(nbr, len + 1);
                    if (nbr == finish){
                        maxLen = len + 1;
                    }
                    myqueue.push(nbr);
                }
            }
        }
        return total;
    }
}mymap;

//复杂度为：n*m
int main(){
    int n, m, i, j;
    char str;
    Position S, E;
    scanf("%d%d\n", &n, &m);
    for (i = 1; i <= n; ++i){
        for (j = 1; j <= m; ++j){
            str = getchar();
            switch (str)
            {
            case 'E': E = Position(i, j); break;
            case 'S': S = Position(i, j); break;
            case 'T': mymap.setMap(Position(i, j), 1); break;
            case '0': break;
            default:mymap.setNum(Position(i, j), str - '0'); break;
            }
        }
        getchar();
    }
    //设置围墙
    for (i = 0; i <= n + 1; ++i){
        mymap.setMap(Position(i, 0), 1);
        mymap.setMap(Position(i, m + 1), 1);
    }
    for (j = 0; j <= m + 1; ++j){
        mymap.setMap(Position(0, j), 1);
        mymap.setMap(Position(n + 1, j), 1);
    }
    printf("%d\n", mymap.findPath(E, S));
    return 0;
}

设计思路与复杂度分析

找到小x的最短路长度，小x一定要走最短路才遭遇最少玩家。因为，如果最短路上能遭遇的玩家，你打算不走最短路去避开他，那么他是可以直接去终点等着你的！然后再考虑逆向思维，所有玩家从终点出发，在小x之前或同时到达自己位置的需要与小x决斗。最终归结为电路布线问题，详细请参考教材。

0%