oj.uz

Submission #72439

# Submission time Handle Problem Language Result Execution time Memory
72439 2018-08-26T08:10:15 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) Aquatic Labyrinth (FXCUP3_aqua) C++17
0 / 100
 62 ms 58052 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

vector<pii> adj[2000005];
priority_queue<pii, vector<pii>, greater<pii> > pq;
int D[2000005];
char A[909][909];
int N;
int R[909][909];
int C[909][909];
int Rc[909][909];
int Cc[909][909];

int cvt(int r, int c, int type) {
	if(type == 0) return (r * N + c) * 2;
	return (c * N + r) * 2 + 1;
}

int main() {
	for(int i = 0; i < 2000005; i++) D[i] = 987654321;

	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%s", A[i]);
	int sx, sy, ex, ey;

	for(int i = 0; i < N; i++) {
		int num = 0;
		int c = 0;
		int j = 0; while(A[i][j] == 'W') j++;

		for( ; j < N; j++) {
			if(A[i][j] == 'W') { c++; if(A[i][j - 1] != 'W') num++; continue; }
			if(A[i][j] == 'M') { sx = i, sy = j; }
			if(A[i][j] == 'H') { ex = i, ey = j; }
			if(j && A[i][j - 1] == 'W') {
				if(num > 0) {
					adj[cvt(i, num, 0)].push_back(pii(cvt(i, num - 1, 0), c * c));
					adj[cvt(i, num - 1, 0)].push_back(pii(cvt(i, num, 0), c * c));
					Rc[i][num] = c * c;
				}
				c = 0;
			}
			R[i][j] = num;
		}
	}

	for(int j = 0; j < N; j++) {
		int num = 0;
		int c = 0;
		int i = 0; while(A[i][j] == 'W') i++;

		for(; i < N; i++) {
			if(A[i][j] == 'W') { c++; if(A[i - 1][j] != 'W') num++; }
			else if(i && A[i - 1][j] == 'W') {
				if(num > 0) {
					adj[cvt(num, j, 1)].push_back(pii(cvt(num - 1, j, 1), c * c));
					adj[cvt(num - 1, j, 1)].push_back(pii(cvt(num, j, 1), c * c));
					Cc[num][j] = c * c;
				}
				c = 0;
			}
			C[i][j] = num;
		}
	}
	/*
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			//printf("%d ", cvt(C[i][j], j, 1));
			printf("%d ", Rc[i][j]);
		}
		puts("");
	}

	for(int i = 0; i < 20; i++) {
		printf("%d: ", i);
		for(pii j : adj[i]) printf("(%d %d) ", j); puts("");
	}*/

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			if(A[i][j] == 'W') continue;

			int now = cvt(i, R[i][j] - 1, 0);
			if(R[i][j] > 0) {
				for(pii k : adj[cvt(C[i][j], j, 1)]) {
					adj[now].push_back(pii(k.first, Rc[i][R[i][j]] + k.second));
				}
			}

			now = cvt(i, R[i][j] + 1, 0);
			for(pii k : adj[cvt(C[i][j], j, 1)]) {
				//printf("%d->%d\n", now, k.first);
				//printf("%d %d %d\n", i, j, k.second);
				adj[now].push_back(pii(k.first, Rc[i][R[i][j] + 1] + k.second));
			}
		}
	}

	for(int j = 0; j < N; j++) {
		for(int i = 0; i < N; i++) {
			if(A[i][j] == 'W') continue;

			int now = cvt(C[i][j] - 1, j, 1);
			if(C[i][j] > 0) {
				for(pii k : adj[cvt(i, R[i][j], 0)]) {
					adj[now].push_back(pii(k.first, Cc[C[i][j]][j] + k.second));
				}
			}

			now = cvt(C[i][j] + 1, j, 1);
			for(pii k : adj[cvt(i, R[i][j], 0)]) {
				adj[now].push_back(pii(k.first, Cc[C[i][j] + 1][j] + k.second));
			}
		}
	}

	for(pii i : adj[cvt(sx, R[sx][sy], 0)]) {
		pq.push(pii(i.second, i.first));
		D[i.first] = i.second;
		//printf("st%d %d\n", i);
	}
	for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
		pq.push(pii(i.second, i.first));
		D[i.first] = i.second;
		//printf("st%d %d\n", i);
	}

	while(!pq.empty()) {
		int nowd = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if(D[now] < nowd) continue;

		for(pii i : adj[now]) {
			int nxt = i.first;
			if(D[nxt] > D[now] + i.second) {
				D[nxt] = D[now] + i.second;
				pq.push(pii(D[nxt], nxt));
			}
		}
	}
	/*
	for(int i = 0; i < 20; i++) {
		printf("%d: ", i);
		for(pii j : adj[i]) printf("(%d %d) ", j); puts("");
	}*/

	int ans = min(D[cvt(ex, R[ex][ey], 0)], D[cvt(C[ex][ey], ey, 1)]);
	printf("%d\n", (ans == 987654321 ? -1 : ans));

	return 0;
}

/*
4
M.W.
.W..
.H..
....
*/

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
aqua.cpp:25:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%s", A[i]);
                             ~~~~~^~~~~~~~~~~~
aqua.cpp:26:10: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sx, sy, ex, ey;
          ^~
aqua.cpp:150:47: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ans = min(D[cvt(ex, R[ex][ey], 0)], D[cvt(C[ex][ey], ey, 1)]);
                                            ~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:124:21: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
                  ~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:26:18: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sx, sy, ex, ey;
                  ^~

Subtask #1
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 55160 KB Output is correct
2 Correct 51 ms 55400 KB Output is correct
3 Correct 59 ms 55644 KB Output is correct
4 Correct 51 ms 56568 KB Output is correct
5 Correct 54 ms 56568 KB Output is correct
6 Correct 61 ms 57412 KB Output is correct
7 Incorrect 62 ms 58052 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 55160 KB Output is correct
2 Correct 51 ms 55400 KB Output is correct
3 Correct 59 ms 55644 KB Output is correct
4 Correct 51 ms 56568 KB Output is correct
5 Correct 54 ms 56568 KB Output is correct
6 Correct 61 ms 57412 KB Output is correct
7 Incorrect 62 ms 58052 KB Output isn't correct
8 Halted 0 ms 0 KB -