Submission #1002210

#TimeUsernameProblemLanguageResultExecution timeMemory
1002210vjudge1Robots (APIO13_robots)C++17
30 / 100
696 ms10836 KiB
#include<iostream> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<queue> #include<deque> using namespace std; #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][305][305]; int tmp = 1; int used[305][305]; pii p[10][305][305]; 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}}; } 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; } } 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}; } } 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}; } } 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}; } } } } //1 > //2 < //3 ^ //4 v bool cmp(pii x , pii y){ return a[x.F][x.S] < a[y.F][y.S]; } 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++){ if(i >= 200)break; int sum = 0; set<pii> st; bool ok = 1; for(int k = 1 ; k < tmp ; k++){ sum += dp[k][i][j]; if(dp[k][i][j] >= inf){ ok = 0; break; } int x = i , y = j; int aa = 200; //cout << x << ' ' << y << '\n'; //cout << v[k - 1].F << ' ' << v[k - 1].S << '\n'; // if(i == 1 and j == 3 and k == 1)cout << x << ' ' << y << '\n'; while(x != v[k - 1].F or y != v[k - 1].S){ aa--; if(!aa)break; auto pp = p[k][x][y]; x = pp.F , y = pp.S; if(!x or !y)break; //if(i == 1 and j == 1 and k == 3)cout << x << ' ' << y << '\n'; //cout << x << ' ' << y << '\n'; st.insert({x , y}); } } // cout << dp[2][i][j] << ' '; // cout << dp[1][i][j] << ' '; //if(len(st) == 0 and ok)cout << i << ' ' << j << '\n'; // if(i == 1 and j == 1 and ok){ // cout << dp[4][i][j] << '\n'; // for(auto it : st)cout << it.F << ' ' << it.S << '\n'; // } if(ok)mn = min(mn , len(st)); } //cout << '\n'; } // cout << p[3][1][1].S; if(mn < inf)cout << mn; else cout << -1; } signed main(){ int t = 1; Bekabot while(t--)skibidi_dop_dop_dop_yes_yes(); }

Compilation message (stderr)

robots.cpp:21:46: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
      |                                              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...