oj.uz

Submission #123206

# Submission time Handle Problem Language Result Execution time Memory
123206 2019-06-30T11:36:52 Z miguel Nautilus (BOI19_nautilus) C++14
66 / 100
 17 ms 1400 KB 
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1000000007;
//#define int ll
int n, m, ss, ans;
set <pi> mp;
bool t[101][101];
bool dp[102][101][101];
string s;

bool valid(int x, int y){
    if(x>0 && x<=n && y>0 && y<=m && t[x][y]) return 1;
    else return 0;
}

void dfs(int x, int y, int cur){
    if(cur==ss){
        if(valid(x, y)) mp.insert({x, y});
    }
    else{
        char c=s[cur];
        if(c=='?'){
            if(valid(x+1, y)) dfs(x+1, y, cur+1);
            if(valid(x, y+1)) dfs(x, y+1, cur+1);
            if(valid(x-1, y)) dfs(x-1, y, cur+1);
            if(valid(x, y-1)) dfs(x, y-1, cur+1);
        }
        else if(c=='S' && valid(x+1, y)) dfs(x+1, y, cur+1);
        else if(c=='E' && valid(x, y+1)) dfs(x, y+1, cur+1);
        else if(c=='N' && valid(x-1, y)) dfs(x-1, y, cur+1);
        else if(c=='W' && valid(x, y-1)) dfs(x, y-1, cur+1);
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>ss;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            if(c=='#') t[i][j]=0;
            else t[i][j]=1;
        }
    }
    cin>>s;
    for(int cur=0; cur<ss; cur++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(valid(i, j) && (cur==0 || dp[cur][i][j])){
                    int x=i, y=j;
                    char c=s[cur];
                    //cout<<c;
                    if(c=='?'){
                        if(valid(x+1, y)) dp[cur+1][x+1][y]=1, x++;
                        x=i; y=j;
                        if(valid(x, y+1)) dp[cur+1][x][y+1]=1, y++;
                        x=i; y=j;
                        if(valid(x-1, y)) dp[cur+1][x-1][y]=1, x--;
                        x=i; y=j;
                        if(valid(x, y-1)) dp[cur+1][x][y-1]=1, y--;
                    }
                    //else cout<<"x";
                    else if(c=='S'){
                        if(valid(x+1, y)) dp[cur+1][x+1][y]=1, x++;
                    }//else cout<<(c=='W');
                    else if(c=='E'){
                        if(valid(x, y+1)) dp[cur+1][x][y+1]=1, y++;
                    }
                    else if(c=='N'){
                        if(valid(x-1, y)) dp[cur+1][x-1][y]=1, x--;
                    }
                    else if(c=='W'){
                        if(valid(x, y-1)) dp[cur+1][x][y-1]=1, y--;
                    }
                }
            }
        }
    } //cout<<endl;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            //cout<<dp[1][i][j];
            if(dp[ss][i][j]) ans++;
        }
        //cout<<endl;
    }
    cout<<ans;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 9 ms 808 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 9 ms 808 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 9 ms 1400 KB Output is correct
8 Correct 11 ms 1272 KB Output is correct
9 Correct 9 ms 1272 KB Output is correct
10 Correct 7 ms 888 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 14 ms 1400 KB Output is correct
13 Correct 15 ms 1372 KB Output is correct
14 Correct 16 ms 1372 KB Output is correct
15 Correct 7 ms 1400 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 16 ms 1400 KB Output is correct
18 Correct 17 ms 1272 KB Output is correct
19 Correct 14 ms 1400 KB Output is correct
20 Correct 8 ms 1272 KB Output is correct
21 Correct 4 ms 760 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 8 ms 1272 KB Output is correct
3 Correct 9 ms 1144 KB Output is correct
4 Correct 9 ms 808 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 9 ms 1400 KB Output is correct
8 Correct 11 ms 1272 KB Output is correct
9 Correct 9 ms 1272 KB Output is correct
10 Correct 7 ms 888 KB Output is correct
11 Correct 4 ms 760 KB Output is correct
12 Correct 14 ms 1400 KB Output is correct
13 Correct 15 ms 1372 KB Output is correct
14 Correct 16 ms 1372 KB Output is correct
15 Correct 7 ms 1400 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 16 ms 1400 KB Output is correct
18 Correct 17 ms 1272 KB Output is correct
19 Correct 14 ms 1400 KB Output is correct
20 Correct 8 ms 1272 KB Output is correct
21 Correct 4 ms 760 KB Output is correct
22 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -