Submission #32087

#	Time	Username	Problem	Language	Result	Execution time	Memory
32087		cheater2k	Portals (BOI14_portals)	C++14	0 / 100	0 ms	25884 KiB

portals

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int inf = 1e9 + 7;

int n, m;
int sx, sy;
int cx, cy;

string a[N];
int d[N][N][2];
const int dx[] = {0, 1, -1, 0}; // {right, down, up, left}
const int dy[] = {1, 0, 0, -1};

int f[N][N][4];

typedef pair<int,int> ii;
void bfs(int id) {
	queue <ii> q;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) d[i][j][id] = inf;
	if (id == 0) d[sx][sy][id] = 0, q.push(ii(sx, sy)); else d[cx][cy][id] = 0, q.push(ii(cx, cy));

	while(!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny] == '#') continue;
			if (d[nx][ny][id] == inf) d[nx][ny][id] = d[x][y][id] + 1, q.push(ii(nx,ny)); 
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i <= m + 1; ++i) a[0] += '#', a[n + 1] += '#';
	for (int i = 1; i <= n; ++i) {
		cin >> a[i]; a[i] = '#' + a[i]; a[i] += '#';
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == 'S') sx = i, sy = j;
			if (a[i][j] == 'C') cx = i, cy = j;
		}
	}

	bfs(0); bfs(1);

	int ans = d[cx][cy][0];

	for (int i = 1; i <= n; ++i) {
		f[i][0][0] = 0, f[i][m + 1][3] = m + 1;
		for (int j = 1; j <= m; ++j) f[i][j][0] = (a[i][j] != '#' ? f[i][j-1][0] : j); // right
		for (int j = m; j >= 1; --j) f[i][j][3] = (a[i][j] != '#' ? f[i][j+1][3] : j); // left
	}

	for (int j = 1; j <= m; ++j) {
		f[0][j][1] = 0, f[n + 1][j][2] = n + 1;
		for (int i = 1; i <= n; ++i) f[i][j][1] = (a[i][j] != '#' ? f[i-1][j][1] : i); // down
		for (int i = n; i >= 1; --i) f[i][j][2] = (a[i][j] != '#' ? f[i+1][j][2] : i); // up
	}

	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (a[i][j] != '#') {
		//cerr << i << ' ' << j << endl;
		for (int dir = 0; dir < 4; ++dir) {
			int ni = i, nj = j;
			if (dir == 0 || dir == 3) nj = f[i][j][dir] + dy[dir];
			if (dir == 1 || dir == 2) ni = f[i][j][dir] + dx[dir];

			ans = min(ans, d[i][j][0] + d[ni][nj][1] + 1); 
			//cerr << "-> " << ni << ' ' << nj << ' ' << d[i][j][0] + d[ni][nj][1] + 1 << endl;
		}
	}

	cout << ans << endl;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30