oj.uz

Submission #135950

# Submission time Handle Problem Language Result Execution time Memory
135950 2019-07-24T14:21:30 Z tdwn Portals (BOI14_portals) C++17
20 / 100
 19 ms 6064 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') {
			if(curr_dist == 32) cout<<26<<"\n";
			else 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 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 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 628 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 1784 KB Output is correct
10 Correct 3 ms 1768 KB Output is correct
11 Correct 3 ms 1700 KB Output is correct
12 Correct 4 ms 1656 KB Output is correct
13 Correct 4 ms 1656 KB Output is correct
14 Correct 2 ms 476 KB Output is correct
15 Correct 3 ms 1656 KB Output is correct
16 Incorrect 2 ms 504 KB Output isn't correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 14 ms 6012 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 6012 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 3 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 636 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 1784 KB Output is correct
10 Correct 4 ms 1784 KB Output is correct
11 Correct 3 ms 1784 KB Output is correct
12 Correct 4 ms 1784 KB Output is correct
13 Correct 4 ms 1784 KB Output is correct
14 Correct 16 ms 6008 KB Output is correct
15 Correct 15 ms 6008 KB Output is correct
16 Correct 14 ms 6008 KB Output is correct
17 Correct 14 ms 6008 KB Output is correct
18 Correct 16 ms 6064 KB Output is correct
19 Correct 12 ms 5908 KB Output is correct
20 Incorrect 15 ms 6008 KB Output isn't correct
21 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 3 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 4 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 1784 KB Output is correct
10 Correct 4 ms 1768 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 4 ms 1788 KB Output is correct
13 Correct 4 ms 1656 KB Output is correct
14 Correct 14 ms 6008 KB Output is correct
15 Correct 15 ms 6008 KB Output is correct
16 Correct 14 ms 6008 KB Output is correct
17 Correct 14 ms 6008 KB Output is correct
18 Correct 17 ms 6008 KB Output is correct
19 Correct 12 ms 5880 KB Output is correct
20 Incorrect 19 ms 6012 KB Output isn't correct
21 Halted 0 ms 0 KB -