Submission #946541

#	Time	Username	Problem	Language	Result	Execution time	Memory
946541		vjudge1	Portals (BOI14_portals)	C++11	0 / 100	1092 ms	2648 KiB

portals

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