oj.uz

답안 #946535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946535 2024-03-14T18:13:18 Z vjudge1 포탈들 (BOI14_portals) C++11
0 / 100
 2 ms 2516 KB 
#include <iostream>

using namespace std;

const int MAX = 1001;
const int INF = 1e6 + 1;

int r, c, sx, sy, ex, ey;
int ans = INF;
int maze[MAX][MAX];
bool vis[MAX][MAX];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};

bool good(int x, int y){
  return x >= 0 && x < r && y >= 0 && y < c && !maze[x][y];
}

void trav(int x, int y, int p, int s){
  if (vis[x][y]) return;
  if (x == ex && y == ey) {
    ans = min(ans, s);
    return;
  }
  vis[x][y] = true;
  for (int i = 0; i < 4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (good(nx, ny)){
      trav(nx, ny, p, s + 1);
    }
    if (p < 2){
      while (good(nx, ny)){
        nx += dx[i];
        ny += dy[i];
      }
      trav(nx - dx[i], ny - dy[i], p + 1, s + 1);
    }
  }
  vis[x][y] = false;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> r >> c;
  char t;
  for (int i = 0; i < r; i++){
    for (int j = 0; j < c; j++){
      cin >> t;
      maze[i][j] = (t == '#' ? 1 : 0);
      if (t == 'S') {
        sx = i;
        sy = j;
      }
      if (t == 'C'){
        ex = i;
        ey = j;
      }
    }
  }
  trav(sx, sy, 0, 0);
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2512 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2516 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -