Submission #413904

#	Time	Username	Problem	Language	Result	Execution time	Memory
413904		Blagojce	Portals (BOI14_portals)	C++11	100 / 100	425 ms	47336 KiB

portals

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const int i_inf = 1e9;	
const ll mod = 1e9+7;
  
const int mxn = 1e3+3;
 
const ll A = 911382323;
const ll B = 972663749;
 
mt19937 _rand(time(NULL));
clock_t z;
 
int n, m;
char a[mxn][mxn];

int d[mxn][mxn];


int dr[4] = {-1, 0, +1, 0};
int dc[4] = {0, +1, 0, -1};


bool inside(int r, int c){
	return (0 <= r && r < n && 0 <= c && c < m);
}
bool portable(int r, int c){
	fr(i, 0, 4){
		int rp = r + dr[i];
		int cp = c + dc[i];
		if(inside(rp, cp) && a[rp][cp] == '#'){
			return true;
		}
	}
	return false;
}
bool vis[mxn][mxn];
void fill_d(){
	
	queue<pii> Q;
	fr(i, 0, n){
		fr(j, 0, m){
			if(a[i][j] == '#') continue;
			if(portable(i, j)){
				vis[i][j] = true;
				Q.push({i, j});
			}
		}
	}
	while(!Q.empty()){
		int r = Q.front().st;
		int c = Q.front().nd;
		Q.pop();
		fr(i, 0, 4){
			int rp = r + dr[i];
			int cp = c + dc[i];
			if(inside(rp, cp) && !vis[rp][cp] && a[rp][cp] != '#'){
				vis[rp][cp] = true;
				d[rp][cp] = d[r][c] + 1;
				Q.push({rp, cp});
			}
		}
	}
}
pii tel[mxn][mxn][4];

void fill_tel(){
	fr(i, 0, n){
		int r = -1, c = -1;
		fr(j, 1, m){
			if(a[i][j] == '#'){
				
				tel[i][j][0] = {-1, -1};
				continue;
			}
			if(a[i][j-1] == '#'){
				r = i, c = j;
			}
			tel[i][j][0] = {r, c};
		}
		r = -1, c = -1;
		for(int j = m-2; j >= 0; j --){
			if(a[i][j] == '#'){	
				tel[i][j][1] = {-1, -1};
				continue;
			}
			if(a[i][j+1] == '#'){
				r = i, c = j;
			}
			tel[i][j][1] = {r, c};
		}
	}
	fr(j, 0, m){
		int r = -1, c = -1;
		fr(i, 1, n){
			if(a[i][j] == '#'){
				tel[i][j][2] = {-1, -1};
				continue;
			}
			if(a[i-1][j] == '#'){
				r = i, c = j;
			}
			tel[i][j][2] = {r, c};
		}
		r = -1, c = -1;
		for(int i = n-2; i >= 0; i --){
			if(a[i][j] == '#'){
				tel[i][j][3] = {-1, -1};
				continue;
			}
			if(a[i+1][j] == '#'){
				r = i, c = j;
			}
			tel[i][j][3] = {r, c};
		}
	}
}



	
int dist[mxn][mxn];
void dijkstra(){
	memset(vis, false, sizeof(vis));
	
	fr(i, 0, n){
		fr(j, 0, m){
			dist[i][j] = n*m;
		}
	}
	int sr, sc;
	fr(i, 0, n){
		fr(j, 0, m){
			if(a[i][j] == 'S'){
				sr = i;
				sc = j;
			}
		}
	}
	
	dist[sr][sc] = 0;
	pq<pair<int, pii> > Q;
	Q.push({0, {sr, sc}});
	while(!Q.empty()){
		int r = Q.top().nd.st;
		int c = Q.top().nd.nd;
		
		Q.pop();
		
		if(vis[r][c])continue;
		vis[r][c] = true;
		
		fr(i, 0, 4){
			int rp = r + dr[i];
			int cp = c + dc[i];
			if(inside(rp, cp) && a[rp][cp] != '#' && dist[r][c] + 1 < dist[rp][cp]){
				dist[rp][cp] = dist[r][c] + 1;
				Q.push({-dist[rp][cp], {rp, cp}});
			}
		}
		fr(i, 0, 4){
			if(tel[r][c][i].st == -1) continue;
			
			int rp = tel[r][c][i].st;
			int cp = tel[r][c][i].nd;
			if(dist[r][c] + d[r][c] + 1< dist[rp][cp]){
				dist[rp][cp] = dist[r][c] + d[r][c] + 1;
				Q.push({-dist[rp][cp], {rp, cp}});
			}
		}
	}
	int er, ec;
	fr(i, 0, n){
		fr(j, 0, m){
			if(a[i][j] == 'C'){
				er = i;
				ec = j;
				break;
			}
		}
	}
	cout<<dist[er][ec]<<endl;
	return;

}


void solve(){
	cin >> n >> m;
	fr(i, 0, n+2) fr(j, 0, m+2) a[i][j] = '#';
	
	fr(i, 1, n+1){
		fr(j, 1, m+1){
			cin >> a[i][j];
		}
	}
	n += 2;
	m += 2;
	
	fill_d();
	fill_tel();
	
	
	
	dijkstra();
	
	
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

Compilation message (stderr)

portals.cpp: In function 'void dijkstra()':
portals.cpp:193:19: warning: 'ec' may be used uninitialized in this function [-Wmaybe-uninitialized]
  193 |  cout<<dist[er][ec]<<endl;
      |                   ^
portals.cpp:193:19: warning: 'er' may be used uninitialized in this function [-Wmaybe-uninitialized]

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