제출 #1159605

#제출 시각아이디문제언어결과실행 시간메모리
1159605ocasuPatkice (COCI20_patkice)C++20
50 / 50
1 ms328 KiB
#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';

    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...