Submission #916992

#TimeUsernameProblemLanguageResultExecution timeMemory
916992vjudge1Nautilus (BOI19_nautilus)C++17
100 / 100
143 ms860 KiB
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
void solve()
{
    int r, c, m;
    cin >> r >> c >> m;
    vector<vector<bool>> grid(r, vector<bool>(c));
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        {
            char c;
            cin >> c;
            if (c == '.')
                grid[i][j] = 0;
            else
                grid[i][j] = 1;
        }
    vector<char> does(m);
    for (int i = 0; i < m; i++)
        cin >> does[i];
    vector<bitset<500>> prev(r);
    // i hate bitstes
    vector<bitset<500>> after(r);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            after[i][j] = !grid[i][j];
    // ja sam mirza bušatlić
    // aprapraprpa
    vector<bitset<500>> next(r);
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            prev[i][j] = !grid[i][j];

    for (int cur = 0; cur < m; cur++)
    {
        for (int i = 0; i < r; i++)
        {
            if (does[cur] == 'W')
            {
                next[i]|=(prev[i]>>1);
            }
            else if (does[cur] == 'S')
            {
                if (i+1 < r)
                    next[i+1]|=prev[i];
            }
            else if (does[cur] == 'E')
            {
                next[i]|=(prev[i]<<1);
            }
            else if (does[cur] == 'N')
            {
                if (i-1 >= 0)
                    next[i-1]|=prev[i];
            }
            else
            {
                next[i]|=(prev[i]<<1);
                if (i+1 < r)
                    next[i+1]|=prev[i];
                next[i]|=(prev[i]>>1);
                if (i-1 >= 0)
                    next[i-1]|=prev[i];
            }        
        }
        for (int i = 0; i < r; i++)
        {
            next[i] &= after[i];
            prev[i] = next[i];
            next[i].reset();
        }
    
    }
    int ans = 0;
    for (int i = 0; i < r; i++)
        ans+=prev[i].count();
    cout << ans << '\n';
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...