oj.uz

Submission #135933

# Submission time Handle Problem Language Result Execution time Memory
135933 2019-07-24T13:55:42 Z tdwn Portals (BOI14_portals) C++17
20 / 100
 15 ms 6008 KB 
#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];

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;
			}
		}
	}

	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] == '#') adj[i][j] = 1;
			//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];
		}
	}
}

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] + 1;
			pq.push(mp(dist[ii][jj]+1, 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;
			//cout<<"Ulaza\n";
			pq.push(mp(dist[ii][jj]+1, 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;
			pq.push(mp(dist[ii][jj]+1, 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;
			pq.push(mp(dist[ii][jj]+1, mp(fu, jj)));
		}
	}

}

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Incorrect 2 ms 504 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 4 ms 1784 KB Output is correct
10 Incorrect 4 ms 1784 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 15 ms 6008 KB Output is correct
6 Correct 15 ms 6008 KB Output is correct
7 Correct 14 ms 6008 KB Output is correct
8 Correct 12 ms 6008 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 732 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 4 ms 1660 KB Output is correct
10 Incorrect 4 ms 1788 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 4 ms 1656 KB Output is correct
10 Incorrect 4 ms 1784 KB Output isn't correct
11 Halted 0 ms 0 KB -