oj.uz

Submission #541713

# Submission time Handle Problem Language Result Execution time Memory
541713 2022-03-24T08:47:48 Z AlperenT Patkice II (COCI21_patkice2) C++17
0 / 110
 7 ms 16084 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5;

struct Point{
    int x, y;

    bool operator != (const Point &sc) const{
        return (x != sc.x) || (y != sc.y);
    }
};

const vector<pair<Point, char>> forv = {{{0, 1}, '>'}, {{1, 0}, 'v'}, {{0, -1}, '<'}, {{-1, 0}, '^'}};

int n, m, dist[N][N];

char arr[N][N];

Point strt, fnsh;

pair<Point, char> par[N][N];

deque<Point> dequ;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> arr[i][j];

            if(arr[i][j] == 'o') strt = {i, j};
            else if(arr[i][j] == 'x') fnsh = {i, j}; 
        }
    }

    memset(dist, -1, sizeof(dist));
    dist[strt.x][strt.y] = 0;

    dequ.push_back(strt);

    while(!dequ.empty()){
        Point v = dequ.front(); dequ.pop_front();

        for(auto p : forv){
            Point e = {v.x + p.first.x, v.y + p.first.y};

            if(e.x >= 1 && e.x <= n && e.y >= 1 && e.y <= m && dist[e.x][e.y] == -1){
                if(arr[v.x][v.y] == 'o' || p.second == arr[v.x][v.y]){
                    dist[e.x][e.y] = dist[v.x][v.y];

                    par[e.x][e.y] = {v, arr[v.x][v.y] == 'o' ? 'o' : p.second};

                    dequ.push_front(e);
                }
                else{
                    dist[e.x][e.y] = dist[v.x][v.y] + 1;

                    par[e.x][e.y] = {v, p.second};

                    dequ.push_back(e);
                }
            }
        }
    }

    cout << dist[fnsh.x][fnsh.y] << "\n";

    while(fnsh != strt){
        arr[par[fnsh.x][fnsh.y].first.x][par[fnsh.x][fnsh.y].first.y] = par[fnsh.x][fnsh.y].second;

        fnsh = par[fnsh.x][fnsh.y].first;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << arr[i][j];
        }
        cout << "\n";
    }
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Incorrect 7 ms 16048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Incorrect 7 ms 16048 KB Output isn't correct
3 Halted 0 ms 0 KB -