제출 #1302007

#제출 시각아이디문제언어결과실행 시간메모리
1302007shivenbhargavaNautilus (BOI19_nautilus)C++20
66 / 100
1096 ms22044 KiB
#include "bits/stdc++.h"
using namespace std;

const int MAXN = 505;
const int MAXM = 5005;

int r,c,m; string direction;
int dir[MAXM];
bool arr[MAXN][MAXN];
queue<tuple<int,int,bool>> q;
unordered_set<string> s;
int xD[4] = {-1,0,1,0};
int yD[4] = {0,1,0,-1};

int main() {
    #ifdef LOCAL
    freopen("submission/input.in", "r", stdin);
    freopen("submission/output.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> r >> c >> m;
    for (int i = 1; i<=r; i++) {
        string s; cin >> s;
        for (int j = 1; j<=c; j++) {
            if (s[j-1] == '.') {
                arr[i][j] = true;
                q.push({i,j,false});
            }
        }
    }
    cin >> direction;
    for (int i = 0; i<m; i++) {
        if (direction[i] == 'N') dir[i] = 0;
        if (direction[i] == 'E') dir[i] = 1;
        if (direction[i] == 'S') dir[i] = 2;
        if (direction[i] == 'W') dir[i] = 3;
        if (direction[i] == '?') dir[i] = -1;
    }
    int dist = 0; bool done = false;
    while (dist!=m) {
        int x = get<0>(q.front()), y = get<1>(q.front()); bool _new = get<2>(q.front()); q.pop();
        if (_new) {
            s.clear();
            dist++;
            done = false;
            if (dist == m) break;
        }
        if (dir[dist] == -1) {
            for (int i = 0; i<4; i++) {
                int curx = x+xD[i], cury = y+yD[i];
                if (curx<=0 || cury<=0 || curx>r || cury>c || !arr[curx][cury] || s.count(to_string(curx)+' '+to_string(cury))!=0) continue;
                s.insert(to_string(curx)+' '+to_string(cury));
                q.push({curx,cury,!done});
                if (!done) done = true;
            }
            continue;
        }
        int curx = x+xD[dir[dist]], cury = y+yD[dir[dist]];
        if (curx<=0 || cury<=0 || curx>r || cury>c || !arr[curx][cury] || s.count(to_string(curx)+' '+to_string(cury))!=0) continue;
        s.insert(to_string(curx)+' '+to_string(cury));
        q.push({curx,cury,!done});
        if (!done) done = true;
    }
    cout << q.size()+1 << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...