Submission #1001985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001985		vjudge1	Robots (APIO13_robots)	C++17	0 / 100	0 ms	348 KiB

robots

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*TAAK ZDES NADO RECURSIU PISAT*/

//MADE BY CHATGPT ANAU MNAU I CHUT CHUT TIMA
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define nep next_permutation
#define itn int
#define reutrn return
#define reutnr return
#define pii pair<int,int>
#define tpii pair<pair<int,int>,int>
#define fpii pair<pair<int,int>,pair<int,int>>
#define sigma signed
#define cni cin
#define cotu cout
#define cotninue continue
#define breka break
#define al(x , y , z) x + z , x + y + z 
#define bits(x) __builtin_popcount(x)
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5;
int mod = 1e9 + 7;
const int modik = 998244353;
const int INF = 1e18;
int n,h,w;
char a[501][501];
map <pii , vector <pii>> g;
map <pii , int> used , dist;
void Tima(){
	cin >> n >> h >> w;
	pii b , e;
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			cin >> a[i][j];
			if(a[i][j] == '1'){
				b = {i , j};
			}
			if(a[i][j] == '2'){
				e = {i , j};
			}
		}
	}
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			if(a[i][j] == 'x') continue;
			bool ok = 0;
			for(int k = i - 1 ; k >= 1 ; k--){
				if(a[k][j] == 'x'){
					ok = 1;
					g[{i , j}].pb({k + 1 , j});
					// g[{k + 1 , j}].pb({i , j});
					break;
				}
				// if(a[k][j] == '1' || a[k][j] == '2'){
					// g[{i , j}].pb({k , j});
				// }
			}
			if(!ok){
				g[{i , j}].pb({1 , j});
				// g[{1 , j}].pb({i , j});
			}
			ok = 0;
			for(int k = i + 1 ; k <= w ; k++){
				if(a[k][j] == 'x'){
					ok = 1;
					g[{i , j}].pb({k - 1 , j});
					// g[{k - 1 , j}].pb({i , j});
					break;
				}
				// if(a[k][j] == '1' || a[k][j] == '2'){
					// g[{i , j}].pb({k , j});
				// }
			}
			if(!ok){
				g[{i , j}].pb({w , j});
				// g[{w , j}].pb({i , j});
			}
			ok = 0;
			for(int k = j - 1 ; k >= 1 ; k--){
				if(a[i][k] == 'x'){
					ok = 1;
					g[{i , j}].pb({i , k + 1});
					// g[{i , k + 1}].pb({i , j});
					break;
				}
				// if(a[i][k] == '1' || a[i][k] == '2'){
					// g[{i , j}].pb({i , k});
				// }
			}
			if(!ok){
				g[{i , j}].pb({i , 1});
				// g[{i , 1}].pb({i , j});
			}
			ok = 0;
			for(int k = j + 1 ; k <= h ; k++){
				if(a[i][k] == 'x'){
					ok = 1;
					g[{i , j}].pb({i , k - 1});
					// g[{i , k - 1}].pb({i , j});
					break;
				}
				// if(a[i][k] == '1' || a[i][k] == '2'){
					// g[{i , j}].pb({i , k});
				// }
			}
			if(!ok){
				g[{i , j}].pb({i , h});
				// g[{i , h].pb({i , j});
			}
		}
	}
	deque <pii> q;
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			dist[{i , j}] = INF;
		}
	}
	q.pb(b);
	used[b] = 1;
	dist[b] = 0; 
	int ans = INF;
	while(q.size()){
		pii v = q.front();
		q.pop_front();
		for(auto to : g[v]){
			if(!used[to]){
				dist[to] = min(dist[v] + 1 , dist[to]);
				// cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << ' ' << dist[v] << ' ' << dist[to] << '\n';
				used[to] = 1; 
				q.pb(to);
			}
		}
	}
	ans = min(ans , dist[e]);
	for(int i = 1 ; i <= w ; i++){
		for(int j = 1 ; j <= h ; j++){
			dist[{i , j}] = INF;
			used[{i , j}] = 0;
		}
	}
	swap(b , e);
	q.pb(b);
	used[b] = 1;
	dist[b] = 0; 
	// ans = INF;
	while(q.size()){
		pii v = q.front();
		q.pop_front();
		for(auto to : g[v]){
			if(!used[to]){
				// cout << v.F << ' ' << v.S << ' ' << to.F << ' ' << to.S << ' ' << a[v.F][v.S] << ' ' << a[to.F][to.S] << '\n';
				dist[to] = min(dist[v] + 1 , dist[to]);
				used[to] = 1; 
				q.pb(to);
			}
		}
	}
	ans = min(ans , dist[e]);
	cout << (ans == INF ? -1 : ans);
}
//It is not important to be better than someone else, but to be better than you were yesterday...
//Push yourself, because no one else is going to do it for you..
sigma main(){
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Tima();
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40