复赛三：棋盘(chess)

洛谷：P3956
OJ：P1458

问题描述

目标：

在一个 m x m 的棋盘上，从起点 (1,1) 移动到终点 (m,m)，计算所需的最小花费。棋盘上的每个格子可能有颜色或无色，移动规则和花费如下：

移动规则与花费：

  1. 移动方向：
    • 只能向 上、下、左、右 四个方向移动（4-方向移动）。
  2. 颜色与花费：
    • 同色移动： 移动到与当前格子颜色相同的格子，花费 0。
    • 异色移动： 移动到颜色不同的格子，花费 1。
    • 无色格子： 移动到无色格子时，可以使用 魔法 将其临时变为 红色 或 黄色，花费 2。但魔法使用后，下一步不能立即再次使用魔法，必须先移动到有色格子后才能再次使用魔法。
  3. 特殊情况：
    • 起点与终点颜色： 起点 (1,1) 必须有颜色，否则无法开始移动。终点 (m,m) 可能有颜色或无色，需根据情况处理。

算法原理：Dijkstra算法

为什么选择Dijkstra算法？

  • 非均匀花费：由于移动花费可以是 0、1 或 2，花费不一致，Dijkstra算法适合用于处理这种具有不同边权的图。
  • 保证最短路径：Dijkstra算法能够确保在每一步都选择当前花费最小的路径，最终找到最小花费的路径。

核心思想：

  1. 状态表示：
    • 每个状态由当前坐标 (x, y)、是否可以使用魔法 can_use_spell 以及当前颜色 color 组成。
  2. 优先队列：
    • 使用优先队列 pq 来选择当前花费最小的节点进行扩展。
  3. 状态扩展：
    • 对于当前节点，尝试向四个方向移动：
      • 有色格子：
        • 计算颜色是否相同，若不同则花费增加 1。
        • 更新状态，can_use_spell 重新设为 1。
      • 无色格子：
        • 如果 can_use_spell 为 1，则可以选择使用魔法：
          • 将无色格子变为红色或黄色，花费增加 2。
          • 根据颜色是否相同，可能再增加 1。
          • 更新状态，can_use_spell 设为 0。
  4. 终点处理：
    • 终点有色：直接取 dis_cost[m][m][*][c] 中的最小值。
    • 终点无色：需要从相邻的左边 (m, m-1) 或上边 (m-1, m) 施放魔法进入终点，计算最小花费。

代码实现：

  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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

// 定义节点结构体
struct Node{
    int x, y;           // 当前坐标
    int can_use_spell;  // 是否可以使用魔法：1 可以，0 不可以
    int color;          // 当前格子的颜色：1 红色，2 黄色
    int cost;           // 当前路径的花费

    // 重载小于运算符，用于优先队列按最小花费排序
    bool operator <(const Node& b) const{
        return cost > b.cost; // 优先队列默认取出最大的元素，所以这里取较小的cost
    }
};

// 定义优先队列
priority_queue<Node> pq;

// 定义移动方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 棋盘格子颜色和最小花费数组
int a[1005][1005]; // a[x][y]: 0 无色，1 红色，2 黄色
int dis_cost[1005][1005][2][3]; // dis_cost[x][y][can_use_spell][color] 最小花费

int m, n;

// Dijkstra算法实现
void dijkstra(){
    // 初始化所有状态的花费为INF
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= m; j++) {
            for(int s = 0; s <= 1; s++) {
                for(int c = 0; c <= 2; c++) {
                    dis_cost[i][j][s][c] = INF;
                }
            }
        }
    }

    // 起点颜色
    int start_color = a[1][1];
    // 起点必须有颜色
    if(start_color == 0){
        // 无法开始
        return;
    }

    // 初始化起点状态
    dis_cost[1][1][1][start_color] = 0;
    pq.push(Node{1, 1, 1, start_color, 0});

    while(!pq.empty()){
        Node cur = pq.top(); pq.pop();

        // 如果当前状态的花费已经大于已记录的最小花费，则跳过
        if(cur.cost > dis_cost[cur.x][cur.y][cur.can_use_spell][cur.color]) continue;

        // 尝试向四个方向移动
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];

            // 检查边界
            if(nx < 1 || nx > m || ny < 1 || ny > m) continue;

            // 下一个格子颜色
            int next_color = a[nx][ny];

            if(next_color != 0){
                // 如果下一个格子有颜色
                int extra_cost = (cur.color != next_color) ? 1 : 0; // 颜色不同则花费1金币
                int total_cost = cur.cost + extra_cost;

                // 下一个状态可以使用魔法（因为是在有颜色的格子上）
                if(dis_cost[nx][ny][1][next_color] > total_cost){
                    dis_cost[nx][ny][1][next_color] = total_cost;
                    pq.push(Node{nx, ny, 1, next_color, total_cost});
                }
            }
            else{
                // 如果下一个格子无色，尝试使用魔法（如果可以）
                if(cur.can_use_spell){
                    // 施放魔法将无色格子变为红色
                    int spell_cost = cur.cost + 2; // 使用魔法的花费
                    int color_after_spell = 1; // 红色
                    int move_cost_red = (cur.color != color_after_spell) ? 1 : 0;
                    int total_cost_red = spell_cost + move_cost_red;

                    if(dis_cost[nx][ny][0][color_after_spell] > total_cost_red){
                        dis_cost[nx][ny][0][color_after_spell] = total_cost_red;
                        pq.push(Node{nx, ny, 0, color_after_spell, total_cost_red});
                    }

                    // 施放魔法将无色格子变为黄色
                    color_after_spell = 2; // 黄色
                    int move_cost_yellow = (cur.color != color_after_spell) ? 1 : 0;
                    int total_cost_yellow = spell_cost + move_cost_yellow;

                    if(dis_cost[nx][ny][0][color_after_spell] > total_cost_yellow){
                        dis_cost[nx][ny][0][color_after_spell] = total_cost_yellow;
                        pq.push(Node{nx, ny, 0, color_after_spell, total_cost_yellow});
                    }
                }
            }
        }
    }
}

int main(){
    //freopen("chess.in","r",stdin);
    //freopen("chess.out","w",stdout);
    
   // ios::sync_with_stdio(false);
   //cin.tie(nullptr);
    int x, y, c;
    cin >> m >> n; // 读取棋盘大小和有颜色的格子数量

    // 初始化棋盘为无色（0）
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= m; j++){
            a[i][j] = 0;
        }
    }

    // 读取有颜色的格子信息
    for(int i = 1; i <= n; i++){
        cin >> x >> y >> c;//c=0代表红色，c=1代表黄色
        // a[x][y] = 0：表示该格子 无色。a[x][y] = 1：表示该格子 红色。a[x][y] = 2：表示该格子 黄色。
        a[x][y] = c + 1; 
    }

    dijkstra(); // 执行Dijkstra算法

    // 处理终点颜色
    if(a[m][m] != 0){
        // 终点有颜色，查看所有可能的状态
        int ans = INF;
        for(int s = 0; s <=1; s++) {
            for(int c = 1; c <=2; c++) {
                ans = min(ans, dis_cost[m][m][s][c]);
            }
        }
        if(ans == INF) cout << "-1\n";
        else cout << ans << "\n";
    }
    else{
        // 终点无色，需要从相邻格子施放魔法进入终点
        int ans = INF;
        // 尝试从左边 (m, m-1) 或上边 (m-1, m) 施放魔法进入 (m,m)
        if(m >1){
            // 从左边 (m, m-1) 施放魔法进入 (m,m)
            for(int c =1; c <=2; c++){
                if(dis_cost[m][m-1][1][c] != INF){
                    // 施法为红色
                    ans = min(ans, dis_cost[m][m-1][1][c] + 2 + ((c != 1) ? 1 : 0));
                    // 施法为黄色
                    ans = min(ans, dis_cost[m][m-1][1][c] + 2 + ((c != 2) ? 1 : 0));
                }
            }
        
        
            // 从上边 (m-1, m) 施放魔法进入 (m,m)
            for(int c =1; c <=2; c++){
                if(dis_cost[m-1][m][1][c] != INF){
                    // 施法为红色
                    ans = min(ans, dis_cost[m-1][m][1][c] + 2 + ((c !=1 ) ? 1 :0));
                    // 施法为黄色
                    ans = min(ans, dis_cost[m-1][m][1][c] + 2 + ((c !=2 ) ? 1 :0));
                }
            }
        }
        if(ans >= INF){
            cout << "-1\n";
        }
        else{
            cout << ans << "\n";
        }
    }

    return 0;
}
Previous Topic
Back to Lesson
Next Quiz