BOJ 16952 - 체스판 여행 2

BOJ 16952 - 체스판 여행 2

열심히 BFS 돌리면 된다.

주의할 것은 어떤 간선으로 가야할지 말아야 할지를 결정하는건데,

      auto go_change = [&](auto a, auto b) -> bool {  
         // 횟수가 2 이상 더 크면 차이나면 무조건 바꾸는게 좋다.  
         if (a.fi > b.fi + 1) return true;  
         // 횟수가 1 차이나면  
         if (a.fi == b.fi + 1 && a.se > b.se + 1) return true;  
         return false;  
      };  
  
      auto go = [&](auto a, auto b) -> bool {  
         // 횟수가 2 이상 더 크면 차이나면 무조건 가는게 좋다.  
         if (a.fi > b.fi + 1) return true;  
         if (a.fi == b.fi + 1 && a.se > b.se) return true;  
         return false;  
      };  

처럼 바꿔줘야 한다.

int n;  
pi dist[11][11][101][3];  
vvi b;  
  
int night_dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};  
int night_dx[] = {1, 2, 2, 1, -1, -2, -2, -1};  
  
void solve() {  
   for (int i = 0; i <= 100; i++)  
      for (int j = 0; j < 3; j++)  
         for (int x = 0; x <= 10; x++)  
            for (int y = 0; y <= 10; y++)  
               dist[y][x][i][j] = {1e9, 1e9};  
  
   cin >> n;  
   b = vvi(n, vi(n));  
   fv2(b);  
  
   int sy, sx;  
   for (int y = 0; y < n; y++)  
      for (int x = 0; x < n; x++) if (b[y][x] == 1) sy = y, sx = x;  
  
   dist[sy][sx][1][0] = dist[sy][sx][1][1] = dist[sy][sx][1][2] = {0, 0};  
  
   queue<array<int, 4>> q;  
   q.push({sy, sx, 1, 0});  
   q.push({sy, sx, 1, 1});  
   q.push({sy, sx, 1, 2});  
  
   while (sz(q)) {  
      auto[y, x, nxt, type] = q.front();  
      q.pop();  
  
      pi cur = dist[y][x][nxt][type];  
  
      auto go_change = [&](auto a, auto b) -> bool {  
         // 횟수가 2 이상 더 크면 차이나면 무조건 바꾸는게 좋다.  
         if (a.fi > b.fi + 1) return true;  
         // 횟수가 1 차이나면  
         if (a.fi == b.fi + 1 && a.se > b.se + 1) return true;  
         return false;  
      };  
  
      auto go = [&](auto a, auto b) -> bool {  
         // 횟수가 2 이상 더 크면 차이나면 무조건 가는게 좋다.  
         if (a.fi > b.fi + 1) return true;  
         if (a.fi == b.fi + 1 && a.se > b.se) return true;  
         return false;  
      };  
  
      for (int t = 0; t < 3; t++) {  
         // ?  
         if (type != t)  
            if (go_change(dist[y][x][nxt][t], cur)) {  
               dist[y][x][nxt][t] = {cur.fi + 1, cur.se + 1};  
               q.push({y, x, nxt, t});  
            }  
      }  
  
      if (type == 0) {  
         for (int d = 0; d < 8; d++) {  
            int ny = y + night_dy[d];  
            int nx = x + night_dx[d];  
            if (ny >= 0 && ny < n && nx >= 0 && nx < n) {  
               int nxt_n = b[ny][nx] == nxt + 1 ? nxt + 1 : nxt;  
  
               // ?  
               if (go(dist[ny][nx][nxt_n][type], cur)) {  
                  dist[ny][nx][nxt_n][type] = {cur.fi + 1, cur.se};  
                  q.push({ny, nx, nxt_n, type});  
               }  
            }  
         }  
      }  
      if (type == 1) {  
         for (int ny = 0; ny < n; ny++) {  
            int nx = x;  
  
            int nxt_n = b[ny][nx] == nxt + 1 ? nxt + 1 : nxt;  
  
            // ?  
            if (go(dist[ny][nx][nxt_n][type], cur)) {  
               dist[ny][nx][nxt_n][type] = {cur.fi + 1, cur.se};  
               q.push({ny, nx, nxt_n, type});  
            }  
         }  
  
         for (int nx = 0; nx < n; nx++) {  
            int ny = y;  
  
            int nxt_n = b[ny][nx] == nxt + 1 ? nxt + 1 : nxt;  
  
            // ?  
            if (go(dist[ny][nx][nxt_n][type], cur)) {  
               dist[ny][nx][nxt_n][type] = {cur.fi + 1, cur.se};  
               q.push({ny, nx, nxt_n, type});  
            }  
         }  
      }  
      if (type == 2) {  
         vi dy = {-1, 1, 1, -1};  
         vi dx = {1, 1, -1, -1};  
         for (int d = 0; d < 4; d++) {  
            for (int k = 1;; k++) {  
               int ny = y + dy[d] * k;  
               int nx = x + dx[d] * k;  
               if (ny >= 0 && ny < n && nx >= 0 && nx < n) {  
                  int nxt_n = b[ny][nx] == nxt + 1 ? nxt + 1 : nxt;  
  
                  // ?  
                  if (go(dist[ny][nx][nxt_n][type], cur)) {  
                     dist[ny][nx][nxt_n][type] = {cur.fi + 1, cur.se};  
                     q.push({ny, nx, nxt_n, type});  
                  }  
               } else break;  
            }  
         }  
      }  
   }  
  
   int ey, ex;  
   for (int y = 0; y < n; y++)  
      for (int x = 0; x < n; x++) if (b[y][x] == n * n) ey = y, ex = x;  
  
   vector<pi> ans = {dist[ey][ex][n * n][0], dist[ey][ex][n * n][1], dist[ey][ex][n * n][2]};  
   sort(all(ans));  
  
   cout << ans[0].fi << ' ' << ans[0].se;  
}