답안 #74412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74412 2018-09-01T05:44:17 Z cheetose 수중 미로 (FXCUP3_aqua) C++11
36 / 100
1394 ms 191072 KB
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define INF 987654321987654321
#define PI 3.14159265358979323846264
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset(a,0,sizeof(a));
#define MEM_1(a) memset(a,-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000009;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int ddx[] = { 0,0,1,1,1,-1,-1,-1 }, ddy[] = { 1,-1,1,0,-1,1,0,-1 };
 
char s[900][901];
VPi v[3240002];
ll dist[3240002];
bool chk[3240002];
int parent[3240002];
int n;
inline int Z(int x,int y,int dir){return dir*n*n+x*n+y;}
const int SS=3240000,EE=3240001;
int main() {
	fill(dist,dist+3240002,INF);
	scanf("%d",&n);
	fup(i,0,n-1,1)scanf("%s",s[i]);
	Pi S,E;
	fup(i,0,n-1,1)
		fup(j,0,n-1,1)
	{
		if(s[i][j]=='M')S=mp(i,j);
		if(s[i][j]=='H')E=mp(i,j);
		if(s[i][j]=='.')
		{
			if(i!=0&&s[i-1][j]!='W')v[Z(i,j,3)].pb(mp(Z(i-1,j,3),0));
			if(i!=n-1&&s[i+1][j]!='W')v[Z(i,j,2)].pb(mp(Z(i+1,j,2),0));
			if(j!=0&&s[i][j-1]!='W')v[Z(i,j,1)].pb(mp(Z(i,j-1,1),0));
			if(j!=n-1&&s[i][j+1]!='W')v[Z(i,j,0)].pb(mp(Z(i,j+1,0),0));
		}
	}
	fup(i,0,n-1,1)
	{
		int t=0, to=-1;
		fdn(j,n-1,0,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)
					fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(j!=0&&s[i][j-1]=='W')
				{
					to=Z(i,j,0);
					t=0;
				}
			}
		}
		t=0, to=-1;
		fup(j,0,n-1,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(j!=n-1 && s[i][j+1]=='W')
				{
					to=Z(i,j,1);
					t=0;
				}
			}
		}
	}
	fup(j,0,n-1,1)
	{
		int t=0, to=-1;
		fdn(i,n-1,0,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(i!=0&&s[i-1][j]=='W')
				{
					to=Z(i,j,2);
					t=0;
				}
			}
		}
		t=0, to=-1;
		fup(i,0,n-1,1)
		{
			if(s[i][j]=='W')t++;
			else
			{
				if(to!=-1)fup(kk,0,3,1)v[Z(i,j,kk)].pb(mp(to,t*t));
				if(i!=n-1&&s[i+1][j]=='W')
				{
					to=Z(i,j,3);
					t=0;
				}
			}
		}
	}
	priority_queue<Pll> q;
	fup(i,0,3,1)
	{
		v[SS].pb(mp(Z(S.X,S.Y,i),0));
		v[Z(E.X,E.Y,i)].pb(mp(EE,0));
	}
	dist[SS] = 0;
	q.push({ 0,SS });
	while (!q.empty())
	{
		ll x = q.top().Y;
		q.pop();
		if (chk[x])continue;
		chk[x] = 1;
		for (const auto& p : v[x])
		{
			ll next = p.X, cost = p.Y;
			if (dist[next] > dist[x]+cost)
			{
				dist[next] = dist[x] + cost;
				parent[next]=x;
				q.push({ -dist[next],next });
			}
		}
	}
	printf("%lld\n",dist[EE]==INF?-1:dist[EE]);
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
aqua.cpp:71:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fup(i,0,n-1,1)scanf("%s",s[i]);
                ~~~~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 101752 KB Output is correct
2 Correct 89 ms 101884 KB Output is correct
3 Correct 86 ms 101928 KB Output is correct
4 Correct 89 ms 102500 KB Output is correct
5 Correct 86 ms 102928 KB Output is correct
6 Correct 91 ms 103312 KB Output is correct
7 Correct 100 ms 103680 KB Output is correct
8 Correct 102 ms 103680 KB Output is correct
9 Correct 98 ms 103680 KB Output is correct
10 Correct 90 ms 103680 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 101752 KB Output is correct
2 Correct 89 ms 101884 KB Output is correct
3 Correct 86 ms 101928 KB Output is correct
4 Correct 89 ms 102500 KB Output is correct
5 Correct 86 ms 102928 KB Output is correct
6 Correct 91 ms 103312 KB Output is correct
7 Correct 100 ms 103680 KB Output is correct
8 Correct 102 ms 103680 KB Output is correct
9 Correct 98 ms 103680 KB Output is correct
10 Correct 90 ms 103680 KB Output is correct
11 Correct 298 ms 119464 KB Output is correct
12 Correct 546 ms 147820 KB Output is correct
13 Incorrect 1394 ms 191072 KB Output isn't correct
14 Halted 0 ms 0 KB -