Submission #135976

#	Time	Username	Problem	Language	Result	Execution time	Memory
135976		tdwn	Portals (BOI14_portals)	C++17	100 / 100	383 ms	32748 KiB

portals

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
#define	P pair<int, pair<int,int> > 
using namespace std;
const int maxn = 1100;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
char maze[maxn][maxn];
int n, m, si, sj, fi, fj;

int fleft[maxn][maxn], fright[maxn][maxn];
int fup[maxn][maxn], fdown[maxn][maxn];

int dist[maxn][maxn];
bool visited[maxn][maxn];

int adj[maxn][maxn];
bool visited_adj[maxn][maxn];

void input() {
	cin>>n>>m;
	for(int i=0;i<=n+1;i++) {
		for(int j=0;j<=m+1;j++) {
			maze[i][j] = '#';
		}
	}

	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>maze[i][j];
		
			if(maze[i][j] == 'S') {
				si = i; sj = j;
			}
			else if(maze[i][j] == 'C') {
				fi = i; fj = j;
			}
		}
	}

	queue<pair<int,int> > q;

	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(maze[i-1][j] == '#' || maze[i+1][j] == '#' || maze[i][j-1] == '#' || maze[i][j+1] == '#') {
				q.push(mp(i, j));	
				adj[i][j] = 0;
				visited_adj[i][j] = true;
			}
			//cout<<adj[i][j];

			if(maze[i][j] == '#') continue;

			if(maze[i-1][j] == '#') fup[i][j] = i;
			else fup[i][j] = fup[i-1][j];

			if(maze[i][j-1] == '#') fleft[i][j] = j;
			else fleft[i][j] = fleft[i][j-1];
 		} //cout<<"\n";
	}

	for(int i=n;i>=1;i--) {
		for(int j=m;j>=1;j--) {
			if(maze[i][j] == '#') continue;

			if(maze[i+1][j] == '#') fdown[i][j] = i;
			else fdown[i][j] = fdown[i+1][j];

			if(maze[i][j+1] == '#') fright[i][j] = j;
			else fright[i][j] = fright[i][j+1];
		}
	}

	while(!q.empty()) {
		pair<int,int> curr = q.front();
		q.pop();

		int ii = curr.first;
		int jj = curr.second;

		for(int d=0;d<4;d++) {
			if(!visited_adj[ii+dx[d]][jj+dy[d]] && maze[ii+dx[d]][jj+dy[d]] != '#') {
				visited_adj[ii+dx[d]][jj+dy[d]] = true;
				adj[ii+dx[d]][jj+dy[d]] = adj[ii][jj] + 1;
				q.push(mp(ii+dx[d], jj+dy[d]));
			}
		}
	}
}

class compare {
public:
	bool operator()(P a, P b) {
		return a.first > b.first;
	}
};

void solve() {
	priority_queue<P, vector<P>, compare>pq;

	for(int i=0;i<=n+1;i++) {
		for(int j=0;j<=m+1;j++) {
			dist[i][j] = 1000000000;
		}
	}

	dist[si][sj] = 0;

	pq.push(mp(0, mp(si, sj)));
	while(!pq.empty()) {
		P curr = pq.top();
		pq.pop();

		int ii = curr.second.first;
		int jj = curr.second.second;
		int curr_dist = curr.first;

		if(maze[ii][jj] == 'C') {
			cout<<curr_dist<<"\n";
			return;
		}

		if(visited[ii][jj]) continue;
		visited[ii][jj] = true;

		//cout<<ii<<" "<<jj<<" - "<<dist[ii][jj]<<"\n";

		for(int d=0;d<4;d++) {
			if(ii + dx[d] >= 1 && ii + dx[d] <= n && jj + dy[d] >= 1 && jj + dy[d] <= m) {
				if(!visited[ii+dx[d]][jj+dy[d]] && dist[ii+dx[d]][jj+dy[d]] > dist[ii][jj] + 1 && maze[ii+dx[d]][jj+dy[d]] != '#') {
					dist[ii+dx[d]][jj+dy[d]] = dist[ii][jj] + 1;
					pq.push(mp(dist[ii][jj]+1, mp(ii+dx[d], jj+dy[d])));
				}
			}
		}

		int fl = fleft[ii][jj];
		if(fl != jj && !visited[ii][fl] && dist[ii][fl] > dist[ii][jj] + 1 + adj[ii][jj]) {
			dist[ii][fl] = dist[ii][jj] + adj[ii][jj] + 1;
			pq.push(mp(dist[ii][jj]+1+ adj[ii][jj], mp(ii, fl)));
		}

		int fr = fright[ii][jj];
		if(fr != jj && !visited[ii][fr] && dist[ii][fr] > dist[ii][jj] + 1 + adj[ii][jj]) {
			dist[ii][fr] = dist[ii][jj] + 1+ adj[ii][jj];
			//cout<<"Ulaza\n";
			pq.push(mp(dist[ii][jj]+1+ adj[ii][jj], mp(ii, fr)));
		}

		int fd = fdown[ii][jj];
		if(fd != ii && !visited[fd][jj] && dist[fd][jj] > dist[ii][jj] + 1 + adj[ii][jj]) {
			dist[fd][jj] = dist[ii][jj] + 1+ adj[ii][jj];
			pq.push(mp(dist[ii][jj]+1+ adj[ii][jj], mp(fd, jj)));
		}

		int fu = fup[ii][jj];
		if(fu != ii && !visited[fu][jj] && dist[fu][jj] > dist[ii][jj] + 1 + adj[ii][jj]) {
			dist[fu][jj] = dist[ii][jj] + 1+ adj[ii][jj];
			pq.push(mp(dist[ii][jj]+1+ adj[ii][jj], mp(fu, jj)));
		}
	}

}

int main() {
	input();
	solve();
}

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