Submission #902550

#	Time	Username	Problem	Language	Result	Execution time	Memory
902550		arashMLG	Patkice II (COCI21_patkice2)	C++17	110 / 110	898 ms	72052 KiB

Main

#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

typedef long long     ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>   pll;

const int N = 2e3 + 23;
const int inf = 1e9;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
// v > ^ <

int n,m;
char a[N][N];
pii par[N][N];
bool mark[N][N];
int dist[N][N];
deque<pii> Q;
int val[300];
priority_queue<pair<int,pii>, vector<pair<int,pii>> , greater<pair<int,pii>>> pq;

void bfs(int x,int y) {
	par[x][y] = {0,0};
	for(int i = 0 ; i< N ; i ++) fill(dist[i],dist[i] + N, inf);
	pq.push({0,{x,y}});
	dist[x][y] = 0;
	while(sz(pq)) {
		auto [x,y] = pq.top().S; pq.pop();
		if(mark[x][y]) continue;
		mark[x][y] = true;
		//if(a[x][y] == 'x') return;
		for(int i = 0 ; i < 4 ; i ++) {
			int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
			int x2=x + dx[i],y2 = y + dy[i];
			debug(x2,y2,w);
			if(x2 < 0 || x2 > n || y2 <0  || y2 > m || mark[x2][y2]) continue;
			if(dist[x][y] +w < dist[x2][y2]) {
				dist[x2][y2] = dist[x][y] + w;
				par[x2][y2] = {x,y};
				pq.push( { dist[x2][y2], {x2,y2}});
			}
		}
	}
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    val['v'] = 0;
    val['>'] = 1;
    val['^'] = 2;
    val['<'] = 3;
	val['.'] = 4;
	val['x'] = val['o'] = 5;
	cin>>n>>m;
	pii start,end;
	for(int i = 1; i <= n; i ++) for(int j= 1; j <= m ;j ++) {
		cin>>a[i][j];
		if(a[i][j] == 'o') {
			start = {i,j};
		} else if(a[i][j] == 'x') {
			end = {i,j};
		}
	}
	bfs(start.F,start.S);
	cout<<dist[end.F][end.S] << '\n';
	int x = end.F,y = end.S;
	while(true) {
		auto [x2,y2] = par[x][y];
		if(a[x][y] == 'o' || a[x2][y2] == 'o') break;
		debug(x,y,par[x][y]);
		if(a[x2][y2] != 'o') {
			if(x2 == x) {
				if(y2+1 == y) {
					a[x2][y2] = '>';
				} else {
					a[x2][y2] = '<';
				}
			} else {
				if(x2+1 == x) {
					a[x2][y2] = 'v';
				} else {
					a[x2][y2] = '^';
				}
			}
		}
		x = x2,y = y2;
	}
	for(int i =1; i <= n ; i++) {
		for(int j = 1; j <= m ; j ++) {
			cout<<a[i][j];
		}
		cout<<'\n';
	}
	return 0;
}

// Jumpsuit, Jumpsuit cover me!
// Jumpsuit, Jumpsuit cover me!

Compilation message (stderr)

Main.cpp: In function 'void bfs(int, int)':
Main.cpp:49:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
      |                  ~~~~~~^
Main.cpp:49:47: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |    int w = ((val[a[x][y]] == i) || (val[a[x][y]] == 5) ? 0 : 1);
      |                                         ~~~~~~^
Main.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
Main.cpp:51:4: note: in expansion of macro 'debug'
   51 |    debug(x2,y2,w);
      |    ^~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
Main.cpp:86:3: note: in expansion of macro 'debug'
   86 |   debug(x,y,par[x][y]);
      |   ^~~~~

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