제출 #1238687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238687		ahmadaltayb	Patkice II (COCI21_patkice2)	C++20	110 / 110	304 ms	67664 KiB

Main

#include<bits/stdc++.h>

using namespace std ;

#define F first
#define S second
#define ll long long
#define f(i , n) for(int i = 0 ; i < n ; i++)
#define a(v) v.begin() , v.end()
#define v(i, n) vector<ll> i(n) ;
#define vov(i, n) vector<vector<ll>> i(n) ;
#define mp(m) map<ll , ll> m ;
const int sz = 1e6 + 9 ;


int main(){
    ios_base::sync_with_stdio(false),cin.tie(nullptr);
    int n , m ;
    cin >> n >> m ;
    vector<vector<int>> wt(n , vector<int>(m , 1)) ;
    vector<vector<int>> dist(n , vector<int>(m , INT_MAX)) ;
    vector<vector<pair<int , int>>> par(n , vector<pair<int ,int>>(m)) ;
    vector<vector<char>> adj(n , vector<char>(m)) ;
    char h ;
    int oi , oj , xi , xj ;
    f(i , n){
        f(j , m){
            cin >> h ;
            adj[i][j] = h ;
            switch (h)
            {
            case 'o' :
                oi = i ;
                oj = j ;
                break;
            case 'x' :
                xi = i ;
                xj = j ;
                break ;
            default:
                break;
            }
        }
    }
    int dx[4] = {1 , -1 , 0 , 0} , dy[4] = {0 , 0 , 1 , -1} ;
    char dir[4] = {'^' , 'v' , '<' , '>'} ;
    dist[oi][oj] = 0 ;
    deque<pair<int , int>> dq ;
    dq.push_front({oi , oj}) ;
    while(!dq.empty()){
        int ui = dq.front().F , uj = dq.front().S ;
        dq.pop_front() ;
        f(i , 4){
            int ui2 = ui + dx[i] ;
            int uj2 = uj + dy[i] ;
            if(ui2 < n && ui2 >= 0 && uj2 < m && uj2 >= 0){
                int wht = 1 ;
                switch (adj[ui][uj]){
                    case 'v' :
                        if(ui2 == ui + 1){
                            wht = 0 ;
                        }
                        break;
                    case '^' :
                        if(ui - 1 == ui2){
                            wht = 0 ;
                        }
                        break;
                    case '>' :
                        if(uj + 1 == uj2){
                            wht = 0 ;
                        }
                        break;
                    case '<' :
                        if(uj - 1 == uj2){
                            wht = 0 ;
                        }
                        break;
                    case 'o' :
                        wht = 0 ;
                        break;
                    default:
                        break;
                }
                if(dist[ui][uj] + wht < dist[ui2][uj2]){
                    dist[ui2][uj2] = dist[ui][uj] + wht ;
                    par[ui2][uj2] = {ui , uj} ;
                    if(wht == 0){
                        dq.push_front({ui2 , uj2}) ;
                    }
                    else{
                        dq.push_back({ui2 , uj2}) ;
                    }
                }
            }
        }
    }
    cout << dist[xi][xj] << endl;
    while(xi != oi || xj != oj){
        f(i , 4){
            int nxi = xi + dx[i] , nxj = xj + dy[i] ;
            int pxi = par[xi][xj].F , pxj = par[xi][xj].S ;
            if(nxi == pxi && nxj == pxj){
                adj[pxi][pxj] = dir[i] ;
                xi = nxi ; xj = nxj ;
                break ;
            }
        }
    }
    adj[oi][oj] = 'o' ;
    f(i , n){
        f(j , m){
            cout << adj[i][j] ;
        }
        cout << endl ;
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80