Submission #946558

#	Time	Username	Problem	Language	Result	Execution time	Memory
946558		vjudge1	Portals (BOI14_portals)	C++11	20 / 100	4 ms	2652 KiB

portals

#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
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30