| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002259 |
2024-06-19T11:35:09 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
71 ms |
97704 KB |
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
#define int long long
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int n , w , h;
char a[505][505];
int dp[10][505][505];
int tmp = 1;
int used[505][505];
pii p[10][505][505];
int rev(int x){
if(x == 1)x = 3;
else if(x == 3)x = 2;
else if(x == 2)x = 4;
else if(x == 4)x = 1;
return x;
}
int inv(int x){
if(x == 1)x = 4;
else if(x == 4)x = 2;
else if(x == 2)x = 3;
else if(x == 3)x = 1;
return x;
}
pair<int , pii> calc(int x , int y , int cur){
while(1){
if(a[x][y] == 'A'){
cur = rev(cur);
}
else if(a[x][y] == 'C'){
cur = inv(cur);
}
if(cur == 1){
if(a[x][y + 1] == 'x' or y + 1 > w)break;
y++;
}
else if(cur == 2){
if(a[x][y - 1] == 'x' or y - 1 == 0)break;
y--;
}
else if(cur == 3){
if(a[x - 1][y] == 'x' or x - 1 == 0)break;
x--;
}
else if(cur == 4){
if(a[x + 1][y] == 'x' or x + 1 > h)break;
x++;
}
}
return {x , {y , cur}};
}
set<pii> g[505][505];
void dfs(int x , int y){
used[x][y] = tmp;
//if(tmp == 2)cout << x << ' ' << y << '\n';
queue<pii> q;
q.push({x , y});
while(len(q)){
int v = q.front().F , u = q.front().S;
used[v][u] = 1;
q.pop();
pair<int , pii> cc = calc(v , u , 1);
int x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1].F = v , p[tmp][x1][y1].S = u;
}
//g[v][u].insert({x1 , y1});
g[x1][y1].insert({v , u});
}
cc = calc(v , u , 2);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
// g[v][u].insert({x1 , y1});
g[x1][y1].insert({v , u});
}
cc = calc(v , u , 3);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
//g[v][u].insert({x1 , y1});
g[x1][y1].insert({v , u});
}
cc = calc(v , u , 4);
x1 = cc.F , y1 = cc.S.F;
if(!used[x1][y1]){
q.push({x1 , y1});
if(dp[tmp][x1][y1] > dp[tmp][v][u] + 1){
dp[tmp][x1][y1] = dp[tmp][v][u] + 1;
p[tmp][x1][y1] = {v , u};
}
//g[v][u].insert({x1 , y1});
g[x1][y1].insert({v , u});
}
}
}
//1 >
//2 <
//3 ^
//4 v
bool cmp(pii x , pii y){
return a[x.F][x.S] < a[y.F][y.S];
}
int ans[12][12][505][505];
void skibidi_dop_dop_dop_yes_yes(){
cin >> n >> w >> h;
vector<pii> v;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
cin >> a[i][j];
dp[1][i][j] = dp[2][i][j] = dp[3][i][j] = dp[4][i][j] = dp[5][i][j] = dp[6][i][j] = dp[7][i][j] = dp[8][i][j] = dp[9][i][j] = inf;
if(a[i][j] >= '1' and a[i][j] <= '9')v.pb({i , j});
}
}
sort(all(v) , cmp);
for(auto it : v){
dp[tmp][it.F][it.S] = 0;
dfs(it.F , it.S);
tmp++;
for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)used[i][j] = 0;
//break;
}
int mn = inf;
if(n == 1){
cout << 0;
return;
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int l = 1 ; l <= n ; l++){
for(int r = 1 ; r <= n ; r++){
ans[i][j][l][r] = inf;
}
}
}
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int k = 1 ; k <= n ; k++){
ans[i][j][k][k] = dp[k][i][j];
}
}
//cout << '\n';
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int l = 1 ; l <= n ; l++){
for(int r = l + 1 ; r <= n ; r++){
for(int md = l ; md < r ; md++){
ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
}
}
}
}
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int l = 1 ; l <= n ; l++){
for(int r = l + 1 ; r <= n ; r++){
for(int md = l ; md < r ; md++){
for(auto it : g[i][j]){
ans[i][j][l][r] = min(ans[i][j][l][r] , ans[it.F][it.S][l][r] + 1);
}
}
}
}
}
}
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int l = 1 ; l <= n ; l++){
for(int r = l + 1 ; r <= n ; r++){
for(int md = l ; md < r ; md++){
ans[i][j][l][r] = min(ans[i][j][l][r] , ans[i][j][l][md] + ans[i][j][md + 1][r]);
}
}
}
}
}
int mx = inf;
//cout << ans[1][1][3][4];
//for(auto it : g[1][1])cout << it.F << ' ' << it.S << '\n';
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
//cout << ans[i][j][1][n] << ' ';
mx = min(mx , ans[i][j][1][n]);
}
// cout << '\n';
}
if(mx < inf)cout << mx;
else cout << -1;
}
signed main(){
int t = 1;
Bekabot
while(t--)skibidi_dop_dop_dop_yes_yes();
}
Compilation message
robots.cpp: In function 'void skibidi_dop_dop_dop_yes_yes()':
robots.cpp:152:6: warning: unused variable 'mn' [-Wunused-variable]
152 | int mn = inf;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12552 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13940 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12552 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13940 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13992 KB |
Output is correct |
| 6 |
Correct |
5 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
4 ms |
12432 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
4 ms |
13996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12552 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13940 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13992 KB |
Output is correct |
| 6 |
Correct |
5 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
4 ms |
12432 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
4 ms |
13996 KB |
Output is correct |
| 11 |
Runtime error |
71 ms |
97704 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
4 ms |
12552 KB |
Output is correct |
| 4 |
Correct |
4 ms |
13940 KB |
Output is correct |
| 5 |
Correct |
4 ms |
13992 KB |
Output is correct |
| 6 |
Correct |
5 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
4 ms |
12432 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12636 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
4 ms |
13996 KB |
Output is correct |
| 11 |
Runtime error |
71 ms |
97704 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
