Submission #72473

#	Time	Username	Problem	Language	Result	Execution time	Memory
72473		BBBSNG (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	861 ms	203088 KiB

aqua

#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];
vector<pii> G[2000005];

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));
					G[cvt(i, num, 0)].push_back(pii(cvt(i, num - 1, 0), c * c));
					G[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));
					G[cvt(num, j, 1)].push_back(pii(cvt(num - 1, j, 1), c * c));
					G[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], 0);

			for(pii k : adj[cvt(C[i][j], j, 1)]) {
				G[now].push_back(pii(k));
			}
		}
	}

	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], j, 1);

			for(pii k : adj[cvt(i, R[i][j], 0)]) {
				G[now].push_back(pii(k));
			}
		}
	}

	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 : G[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..
....

6
M..WW.
W.W.H.
.WW...
W..W.W
.W...W
..W.W.

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

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
aqua.cpp:26: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:115:21: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  for(pii i : adj[cvt(C[sx][sy], sy, 1)]) {
                  ~~~^~~~~~~~~~~~~~~~~~
aqua.cpp:141: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:27:18: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sx, sy, ex, ey;
                  ^~
aqua.cpp:27:10: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int sx, sy, ex, ey;
          ^~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64