Submission #396614

#	Time	Username	Problem	Language	Result	Execution time	Memory
396614		fadi57	Patkice II (COCI21_patkice2)	C++14	55 / 110	328 ms	54020 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int mx=20;
typedef long long ll;
int inf=1e9;
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;
int l=dis[enx][eny];
while(enx!=sx&&eny!=sy){


    int dir=trace[enx][eny];
    enx-=dx[dir];eny-=dy[dir];

   if (dis[enx][eny])
            s[enx][eny] = c[dir];
}
for(int i=0;i<n;i++){
    cout<<s[i]<<endl;
}

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:97:5: warning: unused variable 'l' [-Wunused-variable]
   97 | int l=dis[enx][eny];
      |     ^
Main.cpp:98:14: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 | while(enx!=sx&&eny!=sy){
      |       ~~~~~~~^~~~~~~~~
Main.cpp:98: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 / 30
• Subtask 2: 40 / 80