Submission #1159605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159605		ocasu	Patkice (COCI20_patkice)	C++20	50 / 50	1 ms	328 KiB

patkice

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf=1e12;

signed main(){
    int n,m; cin>>n>>m;
    vector<vector<char>> a(n,vector<char>(m));
    int sR, sC, eR, eC;
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) {
        cin>>a[i][j];
        if (a[i][j]=='o') sR=i, sC=j;
        if (a[i][j]=='x') eR=i, eC=j;
    }
    char best='x';
    int ans=inf;
    queue<pair<int,int>> q;
    
    for (int dr=-1; dr<=1; dr++){
        for (int dc=-1; dc<=1; dc++){
            if (sR+dr<n and sC+dc<m and sR+dr>=0 and sC+dc>=0 and (abs(dr)+abs(dc)==1)){
                bool ok=false;
                q.push({sR+dr,sC+dc});
                int cnt=1;
                while(!q.empty()){
                    cnt++;
                    auto [r,c] = q.front(); q.pop();
                    if (a[r][c]=='^') q.push({r-1,c});
                    else if (a[r][c]=='>') q.push({r,c+1});
                    else if (a[r][c]=='<') q.push({r,c-1});
                    else if (a[r][c]=='v') q.push({r+1,c});
                    else if (a[r][c]=='x'){
                        ok=true;
                        break;
                    }
                }
                char dir = 'x';
                if (dr==1) dir='S';
                if (dr==-1) dir='N';
                if (dc==1) dir='E';
                if (dc==-1) dir='W';

                if (ok and (cnt<ans or cnt==ans and dir<best)){
                    ans=cnt;
                    if (dr==1) best='S';
                    if (dr==-1) best='N';
                    if (dc==1) best='E';
                    if (dc==-1) best='W';
                }
            }
        
        }
    }
    if (best=='x'){
        cout<<":(\n";
    }else{
        cout<<":)\n";
        cout<<best<<'\n';

    }

}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20