Submission #943219

#	Time	Username	Problem	Language	Result	Execution time	Memory
943219		hmm789	Portals (BOI14_portals)	C++14	0 / 100	1 ms	348 KiB

portals

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define INF 1000000000000000000

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int r, c, sx, sy, ex, ey;
	cin >> r >> c;
	string a[r];
	for(int i = 0; i < r; i++) cin >> a[i];
	for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) {
		if(a[i][j] == 'S') sx = i, sy = j;
		if(a[i][j] == 'C') ex = i, ey = j;
	}
	vector<pair<int, int>> adj[r][c];
	bool v[r][c];
	memset(v, 0, sizeof(v));
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(!v[i][j] && a[i][j] != '#' && (i == 0 || a[i-1][j] == '#')) {
			int idx = i;
			while(idx < r && a[idx][j] != '#') v[idx++][j] = 1;
			adj[i][j].push_back({idx-1, j});
			adj[idx-1][j].push_back({i, j});
		}
	}
	memset(v, 0, sizeof(v));
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(!v[i][j] && a[i][j] != '#' && (j == 0 || a[i][j-1] == '#')) {
			int idx = j;
			while(idx < c && a[i][idx] != '#') v[i][idx++] = 1;
			adj[i][j].push_back({i, idx-1});
			adj[i][idx-1].push_back({i, j});
		}
	}
	int dx[4] = {-1, 0, 0, 1};
	int dy[4] = {0, -1, 1, 0};
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) if(a[i][j] != '#') {
			for(int k = 0; k < 4; k++) {
				int nx = i+dx[k], ny = j+dy[k];
				if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if(a[nx][ny] == '#') continue;
				adj[i][j].push_back({nx, ny});
			}
		}
	}
	int dist[r][c];
	memset(dist, -1, sizeof(dist));
	queue<pair<int, int>> q;
	dist[sx][sy] = 0;
	q.push({sx, sy});
	while(!q.empty()) {
		pair<int, int> c = q.front();
		q.pop();
		for(auto i : adj[c.first][c.second]) {
			int nx = i.first, ny = i.second;
			if(dist[nx][ny] == -1 || dist[nx][ny] > dist[c.first][c.second]+1) {
				dist[nx][ny] = dist[c.first][c.second]+1;
				q.push({nx, ny});
			}
		}
	}
	cout << dist[ex][ey];
}

Compilation message (stderr)

portals.cpp: In function 'int32_t main()':
portals.cpp:65:21: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |  cout << dist[ex][ey];
      |                     ^
portals.cpp:65:21: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]

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