Submission #530887

#	Time	Username	Problem	Language	Result	Execution time	Memory
530887		hohohaha	Portals (BOI14_portals)	C++14	20 / 100	25 ms	37452 KiB

portals

#include<bits/stdc++.h> 
using namespace std; 
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (b); i >= (int) (a); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long
const int maxn = 1005, inf = LLONG_MAX / 100ll; 
int n, m, s, c; 
int grid[maxn][maxn]; 
bool adj[maxn][maxn];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; 
bool inside(int i, int j) { 
	return i >= 0 and j >= 0 and i < n and j < m; 
}
bool white(int i, int j) { 
	return inside(i, j) and !grid[i][j]; 
}
int to[maxn][maxn][4]; 
int get_to(int, int, int); 
vector<int> g[maxn * maxn]; 
int dis[maxn * maxn]; 
int get_to(int i, int j, int d) {
	if(to[i][j][d] == -1) {
		if(grid[i][j]) to[i][j][d] = -2; 
		else {
			int ti = i + dx[d], tj = j + dy[d]; 
			if(min(ti, tj) < 0 or max(ti - n, tj - m) >= 0 or grid[ti][tj]) { 
				to[i][j][d] = i * m + j; 
			}
			else to[i][j][d] = get_to(ti, tj, d); 
		}
	}
	return to[i][j][d]; 
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m; 
	fori(i, 0, n - 1)  { 
		fori(j, 0, m - 1) { 
			char c; cin >> c; 
			if(c == '#') { 
				grid[i][j] = 1; 
			}
			else if(c == 'S') { 
				s = i * m + j; 
			}
			else if(c == 'C') { 
				::c = i * m + j; 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				int ti = i + dx[d], tj = j + dy[d]; 
				adj[i][j] |= !white(ti, tj); 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				to[i][j][d] = -1; 
			}
		}
	}
	fori(i, 0, n - 1) { 
		fori(j, 0, m - 1) { 
			fori(d, 0, 3) { 
				if(!grid[i][j]) {
					int temp = get_to(i, j, d); if(temp >= 0 and adj[i][j]) g[i * m + j].eb(temp); 
//					if(i == 3 and 	j == 2) { 
//						cout << adj[i][j] << endl << temp << endl; 
//					}
					int ti = i + dx[d], tj = j + dy[d]; 
					if(white(ti, tj) ) g[i * m + j].eb(ti * m + tj); 
				}
			}
		}
	}
	fill(dis, dis + maxn * maxn, inf); 
	dis[s] = 0; 
	queue<int> q; 
	q.emplace(s); 
	while(q.size()) { 
		int u = q.front(); q.pop(); 
//		cout << u / m << sp << u % m << sp << dis[u] << endl; 
		for(int v: g[u]) { 
			if(dis[v] > dis[u] + 1) { 
				dis[v] = dis[u] + 1; 
				q.emplace(v);
			}
		}
	}
	cout << dis[c]; 
}

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