Submission #70790

#	Time	Username	Problem	Language	Result	Execution time	Memory
70790		imsifile	Aquatic Labyrinth (FXCUP3_aqua)	C++98	100 / 100	1505 ms	288472 KiB

aqua

#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 (stderr)

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]);
   ~~~~~^~~~~~~~~~~~~~~

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