제출 #1187577

#제출 시각아이디문제언어결과실행 시간메모리
1187577omerkingNautilus (BOI19_nautilus)C++20
66 / 100
1095 ms3268 KiB
#include<iostream>
#include<queue>
#include<bitset>
#include<string>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int main(){
    int r,c,m;cin>>r>>c>>m;
    string a[r],s;for(int i=0;i<r;++i)cin>>a[i];cin>>s;
    bitset<500>dp[500];
    queue<pair<int,int>>q;
    for(int i=0;i<r;++i)for(int j=0;j<c;++j)if(a[i][j]=='.')dp[i][j]=1,q.push({i,j});
    for(char ch:s){
        bitset<500>nxt[500];
        queue<pair<int,int>>nq;
        while(!q.empty()){
            auto[x,y]=q.front();q.pop();
            for(int d=0;d<4;++d)if(ch=='?'||"NESW"[d]==ch){
                int nx=x+dx[d],ny=y+dy[d];
                if(nx>=0&&nx<r&&ny>=0&&ny<c&&a[nx][ny]=='.'&&!nxt[nx][ny]){
                    nxt[nx][ny]=1;nq.push({nx,ny});
                }
            }
        }
        swap(dp,nxt);swap(q,nq);
    }
    int ans=0;
    for(int i=0;i<r;++i)ans+=dp[i].count();
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...