#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
typedef long long lld;
struct dd {
int ix; lld v;
dd(int ix_, lld v_){ ix=ix_, v=v_; }
bool operator< (const dd& c) const {
return v>c.v;
}
};
int N, nod[910][910], vcn, st, en;
char mz[910][910];
vector<int> con[3010101], val[3010101];
priority_queue<dd> pq;
lld dist[3010101];
int sq(int a){ return a*a; }
void edge(int s, int e, lld v){
con[s].push_back(e), val[s].push_back(v);
}
int main(){
scanf("%d", &N);
st=en=-1;
for(int i=0; i<N; i++){
scanf("\n%s", mz[i]);
for(int j=0; j<N; j++){
if(mz[i][j]=='W') continue;
else if(mz[i][j]=='M'){
if(st>=0) return 0;
st=vcn;
}
else if(mz[i][j]=='H'){
if(en>=0) return 0;
en=vcn;
}
else if(mz[i][j]=='.'){}
else return 0;
nod[i][j]=vcn++;
}
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(!j || mz[i][j]!='W') continue;
int j2;
for(j2=j; j2<N && mz[i][j2]=='W'; j2++);
if(j2==N) break;
j2--;
for(int k=j-1; k>=0 && mz[i][k]!='W'; k--){
edge(nod[i][k], vcn, sq(j2-j+1));
edge(vcn+1, nod[i][k], 0);
}
for(int k=j2+1; k<N && mz[i][k]!='W'; k++){
edge(nod[i][k], vcn+1, sq(j2-j+1));
edge(vcn, nod[i][k], 0);
}
vcn+=2;
j=j2;
}
for(int j=0; j<N; j++){
if(!j || mz[j][i]!='W') continue;
int j2;
for(j2=j; j2<N && mz[j2][i]=='W'; j2++);
if(j2==N) break;
j2--;
for(int k=j-1; k>=0 && mz[k][i]!='W'; k--){
edge(nod[k][i], vcn, sq(j2-j+1));
edge(vcn+1, nod[k][i], 0);
}
for(int k=j2+1; k<N && mz[k][i]!='W'; k++){
edge(nod[k][i], vcn+1, sq(j2-j+1));
edge(vcn, nod[k][i], 0);
}
vcn+=2;
j=j2;
}
}
for(int i=0; i<vcn; i++) dist[i]=-1;
dist[st]=0, pq.push(dd(st,0));
while(!pq.empty()){
dd x=pq.top(); pq.pop();
if(x.v != dist[x.ix]) continue;
int s=x.ix;
for(int i=con[s].size(); i--;){
int e=con[s][i]; lld v=val[s][i];
if(dist[e]<0 || dist[e]>x.v+v) dist[e]=x.v+v, pq.push(dd(e,x.v+v));
}
}
printf("%lld\n", dist[en]);
return 0;
}
Compilation message
aqua.cpp: In function 'int main()':
aqua.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
aqua.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%s", mz[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
141816 KB |
Output is correct |
| 2 |
Correct |
139 ms |
142024 KB |
Output is correct |
| 3 |
Correct |
130 ms |
142024 KB |
Output is correct |
| 4 |
Correct |
135 ms |
142468 KB |
Output is correct |
| 5 |
Correct |
125 ms |
142472 KB |
Output is correct |
| 6 |
Correct |
135 ms |
143124 KB |
Output is correct |
| 7 |
Correct |
149 ms |
143572 KB |
Output is correct |
| 8 |
Correct |
143 ms |
143572 KB |
Output is correct |
| 9 |
Correct |
137 ms |
144100 KB |
Output is correct |
| 10 |
Correct |
136 ms |
144100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
141816 KB |
Output is correct |
| 2 |
Correct |
139 ms |
142024 KB |
Output is correct |
| 3 |
Correct |
130 ms |
142024 KB |
Output is correct |
| 4 |
Correct |
135 ms |
142468 KB |
Output is correct |
| 5 |
Correct |
125 ms |
142472 KB |
Output is correct |
| 6 |
Correct |
135 ms |
143124 KB |
Output is correct |
| 7 |
Correct |
149 ms |
143572 KB |
Output is correct |
| 8 |
Correct |
143 ms |
143572 KB |
Output is correct |
| 9 |
Correct |
137 ms |
144100 KB |
Output is correct |
| 10 |
Correct |
136 ms |
144100 KB |
Output is correct |
| 11 |
Correct |
286 ms |
155688 KB |
Output is correct |
| 12 |
Correct |
539 ms |
206096 KB |
Output is correct |
| 13 |
Correct |
1067 ms |
207012 KB |
Output is correct |
| 14 |
Correct |
812 ms |
207012 KB |
Output is correct |
| 15 |
Correct |
156 ms |
207012 KB |
Output is correct |
| 16 |
Correct |
1618 ms |
233952 KB |
Output is correct |
| 17 |
Correct |
1594 ms |
233952 KB |
Output is correct |
| 18 |
Correct |
1242 ms |
288516 KB |
Output is correct |
| 19 |
Correct |
1047 ms |
288516 KB |
Output is correct |
| 20 |
Correct |
166 ms |
288516 KB |
Output is correct |
