#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
const int MAX_N = 9e2 + 10;
using ti = tuple<int, int, int, int, int>;
int N;
char Mp[MAX_N][MAX_N];
bool Vis[MAX_N][MAX_N][4];
int Dis[MAX_N][MAX_N][4];
bool check(int x, int y, int d) {
return Vis[x][y][d];
if(Mp[x][y] != 'W') {
bool isConti = false;
for(int k=0; k<4; k++) if(Vis[x][y][k]) isConti = true;
if(isConti) return true;
return false;
}else{
return Vis[x][y][d];
}
}
int main() {
cin >> N;
for(int i=1; i<=N; i++) scanf("%s", Mp[i]+1);
pi st, en;
for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) {
if(Mp[i][j] == 'M') st = pi(i, j);
if(Mp[i][j] == 'H') en = pi(i, j);
for(int k=0; k<4; k++) Dis[i][j][k] = INF;
}
priority_queue<ti, vector<ti>, greater<ti> > Q;
Q.emplace(0, st.one, st.two, 0, 0);
Q.emplace(0, st.one, st.two, 1, 0);
Q.emplace(0, st.one, st.two, 2, 0);
Q.emplace(0, st.one, st.two, 3, 0);
Dis[st.one][st.two][0] = 0;
while(!Q.empty()) {
int dis, x, y, d, cc; tie(dis, x, y, d, cc) = Q.top(); Q.pop();
//if(dis > 0) break;
//printf("%d %d %d %d %d\n", dis, x, y, d, cc);
if(check(x, y, d)) continue; Vis[x][y][d] = true;
//printf("=> %d %d %d %d %d\n", dis, x, y, d, cc);
if(pi(x, y) == en) {
printf("%d\n", dis);
return 0;
}
if(Mp[x][y] != 'W') {
for(int k=d; k<d+1; k++) {
int nx = x + "1012"[k] - '1', ny = y + "0121"[k] - '1';
if(nx <= 0 || ny <= 0 || nx > N || ny > N) continue;
if(check(nx, ny, k)) continue;
if(Mp[nx][ny] != 'W') {
if(Dis[nx][ny][k] > dis) Q.emplace(Dis[nx][ny][k] = dis, nx, ny, k, 0);
}else{
if(Dis[nx][ny][k] > dis+(cc+1)*(cc+1)-cc*cc) Q.emplace(Dis[nx][ny][k] = dis+(cc+1)*(cc+1)-cc*cc, nx, ny, k, cc+1);
}
}
}else{
for(int k=d; k<d+1; k++) {
int nx = x + "1012"[k] - '1', ny = y + "0121"[k] - '1';
if(nx <= 0 || ny <= 0 || nx > N || ny > N) continue;
if(check(nx, ny, k)) continue;
if(Mp[nx][ny] != 'W') {
if(Dis[nx][ny][k] > dis) {
for(int kk=0; kk<4; kk++)
Q.emplace(Dis[nx][ny][k] = dis, nx, ny, kk, 0);
}
}else{
if(Dis[nx][ny][k] > dis+(cc+1)*(cc+1)-cc*cc) Q.emplace(Dis[nx][ny][k] = dis+(cc+1)*(cc+1)-cc*cc, nx, ny, k, cc+1);
}
}
}
}
puts("-1");
return 0;
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:51:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(check(x, y, d)) continue; Vis[x][y][d] = true;
^~
aqua.cpp:51:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(check(x, y, d)) continue; Vis[x][y][d] = true;
^~~
aqua.cpp:34:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=N; i++) scanf("%s", Mp[i]+1);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
