oj.uz

Submission #541715

# Submission time Handle Problem Language Result Execution time Memory
541715 2022-03-24T08:59:49 Z AlperenT Patkice II (COCI21_patkice2) C++17
110 / 110
 300 ms 77620 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5, INF = 1e9 + 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}; 
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dist[i][j] = INF;
        }
    }
    
    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){
                if(arr[v.x][v.y] == 'o' || p.second == arr[v.x][v.y] && dist[v.x][v.y] < dist[e.x][e.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 if(dist[v.x][v.y] + 1 < dist[e.x][e.y]){
                    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";
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:58:70: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |                 if(arr[v.x][v.y] == 'o' || p.second == arr[v.x][v.y] && dist[v.x][v.y] < dist[e.x][e.y]){
      |                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 47 ms 15032 KB Output is correct
7 Correct 51 ms 19552 KB Output is correct
8 Correct 123 ms 32972 KB Output is correct
9 Correct 184 ms 51324 KB Output is correct
10 Correct 274 ms 64824 KB Output is correct
11 Correct 300 ms 77620 KB Output is correct