oj.uz

Submission #396608

# Submission time Handle Problem Language Result Execution time Memory
396608 2021-04-30T12:34:12 Z fadi57 Patkice II (COCI21_patkice2) C++14
55 / 110
 346 ms 57400 KB 
#include<bits/stdc++.h>
using namespace std;
const int mx=20;
typedef long long ll;
int inf=1e6;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
char c[4]={'v','^','>','<'};

int n,m;
bool valid(int x,int y){
if(x>=n||y>=m||x<0||y<0){return 0;}
return 1;

 }

int main(){

cin>>n>>m;
int sx;int sy ;
int enx;int eny;
int b[n][m];
string s[n];
memset(b,-1,sizeof(b));
for(int i=0;i<n;i++){
   cin>>s[i];

    for(int j=0;j<m;j++){
        for(int l=0;l<4;l++){
            if(s[i][j]==c[l]){

                b[i][j]=l;
            }
        }
        if(s[i][j]=='o'){
            sx=i;
            sy=j;
        }
         if(s[i][j]=='x'){
            enx=i;
            eny=j;

        }

    }



 }


deque<pair<int,int>>dq;
int dis[n+2][m+2];
for(int i=0;i<=n;i++){
    for(int j=0;j<=m;j++){

        dis[i][j]=inf;
    }

}
dis[sx][sy]=0;
int trace[n+1][m+1];

dq.push_back({sx,sy});
while(!dq.empty()){
    pair<int,int>me=dq.front();
    int x=me.first;
    int y=me.second;
    dq.pop_front();

    for(int i=0;i<4;i++){
       int nx=me.first+dx[i];
        int ny=me.second+dy[i];
        int cost=dis[x][y];
        if(b[x][y]==i){

        }else{
        cost++;
        }
        if(valid(nx,ny)){


            if(cost<dis[nx][ny]){
                dis[nx][ny]=cost;
                trace[nx][ny]=i;
                if(b[x][y]!=i){
                    dq.push_back({nx,ny});
                }else{
                   dq.push_front({nx,ny});
                 }
            }
        }
    }

 }
cout<<dis[enx][eny]-1<<endl;
while(enx!=sx&&eny!=sy){


    int dir=trace[enx][eny];
    enx-=dx[dir];eny-=dy[dir];
    s[enx][eny]=c[dir];
}
for(int i=0;i<n;i++){
    cout<<s[i]<<endl;
}

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:97:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 | while(enx!=sx&&eny!=sy){
      |       ~~~~~~~^~~~~~~~~
Main.cpp:97:14: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:96:19: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 | cout<<dis[enx][eny]-1<<endl;
      |       ~~~~~~~~~~~~^
Main.cpp:96:19: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Partially correct 1 ms 204 KB Partially correct
4 Correct 1 ms 204 KB Output is correct
5 Partially correct 1 ms 204 KB Partially correct

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Partially correct 1 ms 204 KB Partially correct
4 Correct 1 ms 204 KB Output is correct
5 Partially correct 1 ms 204 KB Partially correct
6 Correct 50 ms 7232 KB Output is correct
7 Partially correct 45 ms 9160 KB Partially correct
8 Partially correct 133 ms 19868 KB Partially correct
9 Correct 198 ms 34804 KB Output is correct
10 Partially correct 316 ms 46364 KB Partially correct
11 Correct 346 ms 57400 KB Output is correct