#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 2e9
using namespace std;
struct xyw{
int x,y,w;
bool operator<(const xyw A)const{
return w>A.w;
}
};
bool mp[999][999];
int dist[999][999];
vector<xyw> edge[999][999];
priority_queue<xyw> pq;
vector<int> st;
int main(){
int n;
int sx,sy,ex,ey;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char c;
scanf(" %c",&c);
if(c=='W') mp[i][j]=1;
if(c=='H') ex=i,ey=j;
if(c=='M') sx=i,sy=j;
}
}
for(int i=1;i<=n;i++){
int cnt=0;
bool sta=1-mp[i][1];
for(int j=1;j<=n;j++){
if(mp[i][j]) sta=0,cnt++;
if(!sta && !mp[i][j]){
while(!st.empty()){
edge[i][st.back()].push_back({i,j,cnt*cnt});
st.pop_back();
}
sta=1,cnt=0;
}
if(sta) st.push_back(j);
}
while(!st.empty()) st.pop_back();
}
for(int i=1;i<=n;i++){
int cnt=0;
bool sta=1-mp[i][n];
for(int j=n;j>=1;j--){
if(mp[i][j]) sta=0,cnt++;
if(!sta && !mp[i][j]){
while(!st.empty()){
edge[i][st.back()].push_back({i,j,cnt*cnt});
st.pop_back();
}
sta=1,cnt=0;
}
if(sta) st.push_back(j);
}
while(!st.empty()) st.pop_back();
}
for(int j=1;j<=n;j++){
int cnt=0;
bool sta=1-mp[1][j];
for(int i=1;i<=n;i++){
if(mp[i][j]) sta=0,cnt++;
if(!sta && !mp[i][j]){
while(!st.empty()){
edge[st.back()][j].push_back({i,j,cnt*cnt});
st.pop_back();
}
sta=1,cnt=0;
}
if(sta) st.push_back(i);
}
while(!st.empty()) st.pop_back();
}
for(int j=1;j<=n;j++){
int cnt=0;
bool sta=1-mp[n][j];
for(int i=n;i>=1;i--){
if(mp[i][j]) sta=0,cnt++;
if(!sta && !mp[i][j]){
while(!st.empty()){
edge[st.back()][j].push_back({i,j,cnt*cnt});
st.pop_back();
}
sta=1,cnt=0;
}
if(sta) st.push_back(i);
}
while(!st.empty()) st.pop_back();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dist[i][j]=INF;
}
dist[sx][sy]=0;
pq.push({sx,sy,0});
while(!pq.empty()){
int px=pq.top().x;
int py=pq.top().y;
pq.pop();
if(px==ex && py==ey){
printf("%d",dist[ex][ey]);
return 0;
}
for(xyw it:edge[px][py]){
if(dist[it.x][it.y]>dist[px][py]+it.w){
dist[it.x][it.y]=dist[px][py]+it.w;
pq.push({it.x,it.y,dist[it.x][it.y]});
}
}
}
printf("-1");
return 0;
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aqua.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&c);
~~~~~^~~~~~~~~~
aqua.cpp:121:12: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
pq.push({sx,sy,0});
~~~~~~~^~~~~~~~~~~
aqua.cpp:121:12: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:128:19: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
printf("%d",dist[ex][ey]);
~~~~~~^~~~~~~~~~~~~~~~~~~
aqua.cpp:128:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
23676 KB |
Output is correct |
2 |
Incorrect |
26 ms |
23916 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
23676 KB |
Output is correct |
2 |
Incorrect |
26 ms |
23916 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |