제출 #1325000

#제출 시각아이디문제언어결과실행 시간메모리
1325000lizaNautilus (BOI19_nautilus)C++20
29 / 100
1012 ms64012 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2")
using namespace std;

int const N=505;
int g[N][N];
int r, c, m;
string s;
set<pair<int,int>> rez;
map<pair<pair<int,int>, int>, int> was;
void f(int x, int y, int xbit, int ybit, int si=0)
{
    if(!g[x][y])return;
    if( was[{{x, y}, si}]==1)return;
    was[{{x, y}, si}]=1;
    if(x+xbit < 0 || x+xbit >= r || y+ybit < 0 || y+ybit >= c) return;
    if(si==m)
    {
        rez.insert({x, y});
        return;
    }
    if(s[si]=='W' || s[si]=='?')
    {
        if(y>0)
        {
            f(x, y-1, xbit, ybit+1, si+1);
        }
    }
    if(s[si]=='N' || s[si]=='?')
    {
        if(x>0)
        {
            f(x-1, y, xbit+1, ybit, si+1);
        }
    }
    if(s[si]=='S' || s[si]=='?')
    {
        if(x<r-1)
        {
            f(x+1, y, xbit-1, ybit, si+1);
        }
    }
    if(s[si]=='E' || s[si]=='?')
    {
        if(y<c-1)
        {
            f(x, y+1, xbit, ybit-1, si+1);
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> c >> m;

    for(int i =0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            char a; cin >> a;
            if(a=='.') g[i][j]=1;
        }
    }
    cin >> s;
    int xbit=0, ybit=0, qu=0;
    for(int i =0; i < m; i++)
    {
        if(s[i]=='N') xbit--;
        if(s[i]=='W') ybit--;
        if(s[i] == 'S') xbit++;
        if(s[i] == 'E') ybit++;
        if(s[i]=='?') qu++;
    }
    if(qu > abs(xbit)) xbit=0;
    else xbit = (abs(xbit)-qu)*(xbit/abs(xbit));
    if(qu > abs(ybit)) ybit=0;
    else ybit = (abs(ybit)-qu)*(ybit/abs(ybit));
    for(int i = 0; i <r; i++)
    {
        for(int j= 0; j < c; j++)
        {
            f(i, j, xbit, ybit);
        }
    }
    cout << rez.size() << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...