BOJ 12887 - 경로 게임

BOJ 12887 - 경로 게임

첫 열부터 마지막 열까지 . 를 거치는 최단경로를 구성한 뒤, 최단경로에 포함되는 . 개수를 총 . 개수에서 빼주면 정답이다.

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
void solve() {
   int n;
   cin >> n;
   vs b(2);
   fv(b);
   vvi dist(2, vi(n, 1e9));
   int white = 0;
   for (int y = 0; y < 2; y++) for (int x = 0; x < n; x++) if (b[y][x] == '.')white++;
   queue<pi> q;
   if (b[0][0] == '.') {
      dist[0][0] = 0;
      q.push({0, 0});
   }
   if (b[1][0] == '.') {
      dist[1][0] = 0;
      q.push({1, 0});
   }
   while (sz(q)) {
      auto [y, x] = q.front();
      q.pop();
      for (int d = 0; d < 4; d++) {
         int ny = y + dy[d], nx = x + dx[d];
         if (ny >= 0 && ny < 2 && nx >= 0 && nx < n && b[ny][nx] == '.' && dist[ny][nx] > dist[y][x] + 1) {
            dist[ny][nx] = dist[y][x] + 1;
            q.push({ny, nx});
         }
      }
   }
   cout << white - min(dist[0][n - 1], dist[1][n - 1]) - 1 << endl;
}