#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);
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;
if(mz[i][j]=='M') st=vcn;
if(mz[i][j]=='H') en=vcn;
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:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%s", mz[i]);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
141688 KB |
Output is correct |
2 |
Correct |
122 ms |
141796 KB |
Output is correct |
3 |
Correct |
135 ms |
141960 KB |
Output is correct |
4 |
Correct |
141 ms |
142480 KB |
Output is correct |
5 |
Correct |
142 ms |
142480 KB |
Output is correct |
6 |
Correct |
129 ms |
142936 KB |
Output is correct |
7 |
Correct |
138 ms |
143572 KB |
Output is correct |
8 |
Correct |
131 ms |
143572 KB |
Output is correct |
9 |
Correct |
141 ms |
144212 KB |
Output is correct |
10 |
Correct |
133 ms |
144212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
141688 KB |
Output is correct |
2 |
Correct |
122 ms |
141796 KB |
Output is correct |
3 |
Correct |
135 ms |
141960 KB |
Output is correct |
4 |
Correct |
141 ms |
142480 KB |
Output is correct |
5 |
Correct |
142 ms |
142480 KB |
Output is correct |
6 |
Correct |
129 ms |
142936 KB |
Output is correct |
7 |
Correct |
138 ms |
143572 KB |
Output is correct |
8 |
Correct |
131 ms |
143572 KB |
Output is correct |
9 |
Correct |
141 ms |
144212 KB |
Output is correct |
10 |
Correct |
133 ms |
144212 KB |
Output is correct |
11 |
Correct |
280 ms |
155604 KB |
Output is correct |
12 |
Correct |
531 ms |
205880 KB |
Output is correct |
13 |
Correct |
1066 ms |
207000 KB |
Output is correct |
14 |
Correct |
716 ms |
207000 KB |
Output is correct |
15 |
Correct |
134 ms |
207000 KB |
Output is correct |
16 |
Correct |
1446 ms |
233852 KB |
Output is correct |
17 |
Correct |
1476 ms |
234084 KB |
Output is correct |
18 |
Correct |
1118 ms |
288612 KB |
Output is correct |
19 |
Correct |
732 ms |
288612 KB |
Output is correct |
20 |
Correct |
127 ms |
288612 KB |
Output is correct |