Submission #1293036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293036		Minbaev	로봇 (APIO13_robots)	C++20	30 / 100	1 ms	576 KiB

robots

#include <bits/stdc++.h>

using namespace std;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
#define ar      array

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

namespace FAST {
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 3e18 + 7;
const int mod = 1e9 + 7;
const int N = 6e5 + 5;
const int md = 998244353;

int n,m,k;
vector<int>dx = {-1, 0, 1, 0};
vector<int>dy = {0, 1, 0, -1};
char arr[25][25];
vector<ar<int,2>>g[25][25];

void djk(vector<vector<int>>&dp, int i, int j){
	queue<ar<int,2>>q;
	q.push({i, j});
	dp[i][j] = 0;
	
	while(!q.empty()){
		auto [x, y] = q.front();
		q.pop();
		
		for(auto [a, b] : g[x][y]){
			if(umin(dp[a][b], dp[x][y] + 1)){
				q.push({a, b});
			}
		}
	}
}

ar<int,2> dir(int i, int j, int type){
	if(arr[i][j] == 'C'){
		type += 1;
		type %= 4;
	}
	if(arr[i][j] == 'A'){
		type -= 1;
		if(type < 0)type += 4;
	}
	
	i += dx[type];
	j += dy[type];
	
	if(j <= 0 || j > m || i <= 0 || i > n || arr[i][j] == 'x'){
		i -= dx[type];
		j -= dy[type];
		return {i, j};
	}
	return dir(i, j, type);
}

void solve(){
	
	cin >> k >> m >> n;
	
	
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> arr[i][j];
			//~ cout << arr[i][j];
		}
		//~ cout << "\n";	
	}
	
	if(k != 2){
		cout << -1 << "\n";
		return;
	}
	
	vector<vector<int>>dp1(n + 1, vector<int>(m + 1, inf)), dp2(n + 1, vector<int>(m + 1, inf));
	
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			for(int l = 0;l<4;l++){
				ar<int,2>aa = dir(i, j, l);
				g[i][j].pb(aa);
			}
		}
	}
	
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			if(0 <= (arr[i][j] - '0') && (arr[i][j] - '0') <= 9){
				if(arr[i][j] == '1')djk(dp1, i, j);
				else djk(dp2, i, j);
			}
		}
	}
	
	int res = inf;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			umin(res, dp1[i][j] + dp2[i][j]);
		}
	}
	
	if(res == inf){
		cout << -1 << "\n";
		return;
	}
	
	cout << res << "\n";
	
}
/*
4 10 5
..........
AA...x....
..A..x....
2....x....
..C.1.A...



*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;//cin >> tt;
    while(tt--){solve();}//cout << '\n';}	

}

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