oj.uz

Submission #946558

# Submission time Handle Problem Language Result Execution time Memory
946558 2024-03-14T18:31:19 Z vjudge1 Portals (BOI14_portals) C++11
20 / 100
 4 ms 2652 KB 
#include <iostream>
#include <vector>
#include <queue>

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){
  queue<vector<int>> q;
  q.push({x, y, 0});
  vis[x][y] = true;
  while (!q.empty()){
    vector<int> t = q.front();
    q.pop();
    int a = t[0];
    int b = t[1];
    int s = t[2];
    if (a == ex && b == ey){
      cout << s << '\n';
      return;
    }
    for (int i = 0; i < 4; i++){
      int nx = a + dx[i];
      int ny = b + dy[i];
      if (good(nx, ny) && !vis[nx][ny]){
        q.push({nx, ny, s + 1});
        vis[nx][ny] = true;
      }
      while (good(nx, ny)){
        nx += dx[i]; ny += dy[i];
      }
      nx -= dx[i]; ny -= dy[i];
      if (!vis[nx][ny]){
        q.push({nx, ny, s + 1});
        vis[nx][ny] = true;
      }
    }
  }
}

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);
  return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2548 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 4 ms 2648 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Incorrect 0 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -