oj.uz

답안 #946541

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946541 2024-03-14T18:18:47 Z vjudge1 포탈들 (BOI14_portals) C++11
0 / 100
 1000 ms 2648 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};
int port();

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 s){
  if (x == ex && y == ey) {
    ans = min(ans, s);
    return;
  }
  if (vis[x][y]) 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, s + 1);
    }
    while (good(nx, ny)){
      nx += dx[i];
      ny += dy[i];
    }
    trav(nx - dx[i], ny - dy[i], 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);
  cout << ans << '\n';
  return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 20 ms 2524 KB Output is correct
5 Execution timed out 1079 ms 2392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 20 ms 2396 KB Output is correct
5 Execution timed out 1063 ms 2396 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Execution timed out 1092 ms 2396 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 19 ms 2520 KB Output is correct
5 Execution timed out 1078 ms 2396 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2596 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 20 ms 2396 KB Output is correct
5 Execution timed out 1070 ms 2396 KB Time limit exceeded
6 Halted 0 ms 0 KB -