제출 #1175791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175791		akuyga	Mecho (IOI09_mecho)	C++20	1 / 100	290 ms	131072 KiB

mecho

#include "bits/stdc++.h"
using namespace std;
#define ii pair<ll,ll>
#define f first
#define s second
#define mp make_pair
#define ll long long

vector<ii> ways={mp(0,1),mp(1,0),mp(0,-1),mp(-1,0)};

int main(){
    int N,S;
    cin>>N>>S;
    vector<vector<bool>> b(N,vector<bool>(N,1));
    vector<vector<int>> A(N,vector<int>(N,-1));
    queue<ii> QB;
    int px,py,gx,gy;
    string s;
    for(int i=0;i<N;i++){
        cin>>s;
        for(int j=0;j<N;j++){
            if(s[j]=='T')b[i][j]=0;
            else if(s[j]=='H'){b[i][j]=0; QB.push(mp(i,j));}
            else if(s[j]=='M'){px=i; py=j;}
            else if(s[j]=='D'){gx=i; gy=j;}
        }
        
    }
    queue<pair<ii,ii>> Q;
    Q.push(mp(mp(S,0),mp(px,py)));
    //f.f is step left
    //f.s is t baby;
    A[px][py]=1;
    int T=0;
    while(!Q.empty()){
        int t=Q.front().f.s;
        int step=Q.front().f.f;
        ii curr=Q.front().s;
        //cout<<curr.f<<' '<<curr.s<<'\n';
        Q.pop();
        if(curr.f==gx&&curr.s==gy)continue;
        if(t>T){
            T=t;
            queue<ii> temp;
            while(!QB.empty()){
                ii bq=QB.front();
                QB.pop();
                for(auto i:ways)
                    if(bq.f+i.f>=0&&bq.f+i.f<N&&bq.s+i.s>=0&&bq.s+i.s<N&&b[bq.f+i.f][bq.s+i.s]){
                        temp.push(mp(bq.f+i.f,bq.s+i.s));
                        b[bq.f+i.f][bq.s+i.s]=0;
                    }
            }
            QB=temp;
        }
        if(step==0){step=S; t++;}
        for(auto i:ways)
            if(curr.f+i.f>=0&&curr.f+i.f<N&&curr.s+i.s>=0&&curr.s+i.s<N&&b[curr.f+i.f][curr.s+i.s]){
                A[curr.f+i.f][curr.s+i.s]=A[curr.f][curr.s];
                Q.push(mp(mp(step-1,t),mp(curr.f+i.f,curr.s+i.s)));
            }
        if(b[px][py]){A[px][py]++; Q.push(mp(mp(S,t+1),mp(px,py)));}
    }
    // for(int i=0;i<N;i++){
    //     for(int j=0;j<N;j++)cout<<A[i][j]<<' ';
    //     cout<<'\n';
    // }
    cout<<A[gx][gy];
}

• Subtask 1: 1 / 100