oj.uz

Submission #465672

# Submission time Handle Problem Language Result Execution time Memory
465672 2021-08-16T16:12:26 Z AnasBenMoussa Portals (BOI14_portals) C++14
0 / 100
 113 ms 262148 KB 
#include <bits/stdc++.h>

typedef double db ;
using namespace std;
#define all(x) begin(x), end(x)
#define pb push_back
#define int long long
#define doub(k) printf("%.1lf\n", k) // setprecision(5)
typedef pair<int ,int > pll;typedef map<int , int > mll;typedef vector<int > vll;typedef vector<pll>vpll;
 typedef set<int > sll;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};
const int dr[8] = {1,1,0,-1,-1,-1, 0, 1}, dc[8] = {0,1,1, 1, 0,-1,-1,-1};
//vector<char>v{'R','B','G'};
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
vector<vector<pair<int,int>>> path;int cyt;int cye;
char grid[10000][100000];int x,y;pll star,en;int vis[10000][10000];
int  solve(int n,int j){

    //cout<<n<< " "<<j<<endl;


    if(n==en.first&&j==en.second){
        return -2;
    }
    if(n<0||n>x||j<0||j>y){
        return INT_MAX;
    }
    if(grid[n][j]=='#'){
        return INT_MAX;
    }



    int ans=INT_MAX;
    //cout<<ans<<endl;
        for(int i=1;i<=max(x,y);i++){

            if(grid[n][j+i]!='#'&&grid[n][j+i+1]=='#'){
                 if(n<=0||j+i<=0||n>x||j+i>y){
                    continue;
                }
                if(vis[n][j+i]){
                    continue;
                }
                vis[n][j+i]=1;
                ans=min(ans,solve(n,j+i))+1;
                vis[n][j+i]=0;
            }
        }
        for(int i=1;i<=max(x,y);i++){
            if(grid[n][j-i]!='#'&&grid[n][j-i-1]=='#'){
                 if(n<=0||j-i<=0||n>x||j-i>y){
                    continue;
                }
                if(vis[n][j-i]){
                    continue;
                }
                vis[n][j-i]=1;
                ans=min(ans,solve(n,j-i))+1;
                vis[n][j-i]=0;
            }
        }
        for(int i=1;i<=max(x,y);i++){
            if(grid[n+i][j]!='#'&&grid[n+i+1][j]=='#'){
                 if(n+i<=0||j<=0||n+i>x||j>y){
                    continue;
                }
                if(vis[n+i][j]){
                    continue;
                }
                vis[n+i][j]=1;
                ans=min(ans,solve(n+i,j))+1;
                vis[n+i][j]=0;
            }
        }
        for(int i=1;i<=max(x,y);i++){
            if(grid[n-i][j]!='#'&&grid[n-i-1][j]=='#'){
                if(n-i<=0||j<=0||n-i>x||j>y){
                    continue;
                }
                if(vis[n-i][j]){
                    continue;
                }
                vis[n-i][j]=1;

                ans=min(ans,solve(n-i,j))+1;
                vis[n-i][j]=0;
            }
        }
         for(int r=0;r<4;r++){
        if(n+nx[r]<=0||n+nx[r]>x||j+ny[r]<=0||j+ny[r]>y){
            continue;
        }

        if(vis[n+nx[r]][j+ny[r]]){
            continue;
        }
        vis[n+nx[r]][j+ny[r]]=1;
        ans=min(ans,solve(n+nx[r],j+ny[r]))+1;
         vis[n+nx[r]][j+ny[r]]=0;

    }
    return ans;

}
    int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin>>x;
    cin>>y;
    memset(grid,'#',sizeof(grid));
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            char t;cin>>t;
            if(t=='S'){
                star={i,j};
            }
            if(t=='C'){
                en={i,j};
            }
            grid[i][j]=t;
        }
    }
    //cout<<grid[x][1]<<endl;
    cout<<solve(star.first,star.second)<<endl;
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 113 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -