Submission #72487

#	Time	Username	Problem	Language	Result	Execution time	Memory
72487		호우주의보 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	153 ms	4216 KiB

aqua

//#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
using namespace std;
int N,M,er,ec,MP[900][900];
struct A;
priority_queue<A,vector<A>,greater<A> >PQ;
struct A
{
    int CS,r,c;
    bool operator>(const A&Tt)const{return CS>Tt.CS;}
    void FF(int dr,int dc)const
    {
        int rr=r+dr,cc=c+dc,le=0,mini=CS+1;
        for(;0<=rr&&rr<N&&0<=cc&&cc<N&&MP[rr][cc]!=-1;rr+=dr,cc+=dc)mini=min(mini,MP[rr][cc]);
        if(mini<=CS)return;
        for(;0<=rr&&rr<N&&0<=cc&&cc<N&&MP[rr][cc]==-1;le++,rr+=dr,cc+=dc);
        for(le=CS+le*le;0<=rr&&rr<N&&0<=cc&&cc<N&&MP[rr][cc]!=-1;rr+=dr,cc+=dc)
            if(MP[rr][cc]>le)
            {
      //          printf("uped %d %d - > %d %d :: %d -> %d\n",r,c,rr,cc,MP[rr][cc],le);
                PQ.push({MP[rr][cc]=le,rr,cc});

            }
    }
};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    string S;
    for(int i=0;i<N;i++)
    {
        cin>>S;
        for(int j=0;j<N;j++)
        {
            MP[i][j]=(S[j]=='W'?-1:1<<30);
            if(S[j]=='M')
                PQ.push({MP[i][j]=0,i,j});
            else if(S[j]=='H')
                er=i,ec=j;
        }
    }
    while(!PQ.empty())
    {
        A TT=PQ.top();PQ.pop();
        if(TT.r==er&&TT.c==ec){printf("%d",TT.CS);return 0;}
     //   printf("%d %d :: %d & %d\n",TT.r,TT.c,MP[TT.r][TT.c],TT.CS);
        if(TT.CS==MP[TT.r][TT.c])
        {
            TT.FF(1,0);
            TT.FF(-1,0);
            TT.FF(0,1);
            TT.FF(0,-1);
        }
    }
    printf("-1 ");
}

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