复赛三：棋盘(chess)

  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;
}