2024乔斯复赛集训九连测-(第八场)

#include <bits/stdc++.h>
using namespace std;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
const int N = 1e3 + 5;

struct Node { int x, y, t; };       //t记录穿过虫洞的次数

int n, m, k, sx, sy, x2, y2;
vector<Node> G[N];

int g[N][N], dis[N][N][6]; //dis i, j, k表示从起点到达(i, j)，经过k次虫洞的最少耗费电量
int vis[N][6];   //是否在第j轮穿过虫洞的时候，穿过了该颜色为i的虫洞，需要多加一维，因为到达某个编号的虫洞，剩余的虫洞使用次数不同，也会对应不同的情况

void spfa() {
  queue<Node> q;
  memset(dis, 127, sizeof dis);     //初始化为无穷大
  dis[sx][sy][0] = 0; 
  q.push({sx, sy, 0});
  while(q.size()) {
    Node u = q.front(); q.pop();
    
    //走虫洞的走法
    if(u.t < k && !vis[g[u.x][u.y]][u.t]) {
      for (auto p : G[g[u.x][u.y]]) {
        if(dis[p.x][p.y][u.t + 1] > dis[u.x][u.y][u.t]) {
          dis[p.x][p.y][u.t + 1] = dis[u.x][u.y][u.t];
          q.push({p.x, p.y, u.t + 1});
        }
      }
      vis[g[u.x][u.y]][u.t] = 1;
    }
    //走周围的走法
    for (int i = 0; i < 4; i++) {
      int nx = u.x + dx[i], ny = u.y + dy[i];
      if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
      if(dis[nx][ny][u.t] > dis[u.x][u.y][u.t] + 1) {
        dis[nx][ny][u.t] = dis[u.x][u.y][u.t] + 1;
        q.push({nx, ny, u.t});
      }
    }
  }
}
int main() {
  freopen("hole.in", "r", stdin);
  freopen("hole.out", "w", stdout);
  cin >> n >> m >> k >> sx >> sy >> x2 >> y2;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> g[i][j];
      G[g[i][j]].push_back({i, j});
    }
  }
  spfa();
  int ans = INT_MAX;
  for (int i = 0; i <= k; i++) ans = min(ans, dis[x2][y2][i]);
  cout << ans;
  return 0;
}

我们会在赛后检查代码相似度。