Submission #541715

#	Time	Username	Problem	Language	Result	Execution time	Memory
541715		AlperenT	Patkice II (COCI21_patkice2)	C++17	110 / 110	300 ms	77620 KiB

Main

#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 (stderr)

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 / 30
• Subtask 2: 80 / 80