AB路线——BFS+分层图

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
int g[N][N];
int dist[N][N][11];
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
int n, m, k;
void bfs()
{
  memset(dist, 0x3f, sizeof dist);
  dist[1][1][1] = 1;
  queue<array<int, 3>> q;
  q.push({1, 1, 1});

  while (q.size())
  {
    auto u = q.front();
    q.pop();
    int x = u[0], y = u[1], s = u[2];
    int d = dist[x][y][s];
    for (int i = 0; i < 4; i++)
    {
      int nx = x + dx[i], ny = y + dy[i], nc = d / k % 2, ns = (s + 1) % k;
      if (nx < 1 || ny < 1 || nx > n || ny > m || nc != g[nx][ny])
        continue;
      if (dist[nx][ny][ns] > d + 1)
      {
        dist[nx][ny][ns] = d + 1;
        q.push({nx, ny, ns});
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
  {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++)
    {
      g[i][j + 1] = (s[j] != 'A');
    }
  }

  bfs();

  int ans = inf;
  for (int i = 0; i < k; i++)
    ans = min(ans, dist[n][m][i]);

  if (ans == inf)
    ans = -1;
  else
    ans -= 1;
  cout << ans;
}