Submission #1002455

#TimeUsernameProblemLanguageResultExecution timeMemory
1002455vjudge1Robots (APIO13_robots)C++17
0 / 100
3 ms6488 KiB
#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 h , w , n; int ans[10][10][505][505]; int dp[505][505]; int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1}; char a[505][505]; vector<pii> g[505][505]; pii id[10]; pii s[505][505][5]; bool p(int x , int y){ if(1 <= x and x <= h and 1 <= y and y <= w and a[x][y] != 'x')return 1; return 0; } pii fnd(int x , int y , int t){ if(s[x][y][t].F and s[x][y][t].S)return s[x][y][t]; s[x][y][t] = {-inf , -inf}; int tt = t; if(a[x][y] == 'A'){ tt = (tt + 1) % 4; } else if(a[x][y] == 'C'){ tt = (tt + 3) % 4; } int x1 = x + dx[tt] , y1 = y + dy[tt]; if(p(x1 , y1))return s[x][y][t] = fnd(x1 , y1 , tt); else return s[x][y][t] = {x , y}; } void build(){ for(int i = 1 ; i <= h ; i++){ for(int j = 1 ; j <= w ; j++){ if(a[i][j] == 'x')continue; for(int t = 0 ; t <= 3 ; t++){ pii aa = fnd(i , j , t); if(a[i][j] != 'x' and aa.F > 0)g[i][j].pb(aa); } } } } void skibidi_dop_dop_dop_yes_yes(){ cin >> n >> w >> h; for(int i = 1 ; i <= h ; i++){ for(int j = 1 ; j <= w ; j++){ cin >> a[i][j]; if(a[i][j] >= '1' and a[i][j] <= '9')id[a[i][j] - '0'] = {i , j}; } } build(); for(int l = 1 ; l <= n ; l++){ for(int r = 1 ; r <= n ; r++){ for(int i = 1 ; i <= h ; i++){ for(int j = 1 ; j <= w ; j++){ ans[l][r][i][j] = inf; } } } } for(int i = 1 ; i <= n ; i++){ ans[i][i][id[i].F][id[i].S] = 0; } for(int ll = 1 ; ll <= n ; ll++){ for(int l = 1 ; l + ll - 1 <= n ; l++){ int r = l + ll - 1; set<pair<int , pii>> st; for(int i = 1 ; i <= h ; i++){ for(int j = 1 ; j <= w ; j++){ for(int md = l ; md < r ; md++){ ans[l][r][i][j] = min(ans[l][r][i][j] , ans[l][md][i][j] + ans[md + 1][r][i][j]); } if(ans[l][r][i][j] != inf)st.insert({ans[l][r][i][j] , {i , j}}); } } while(len(st)){ auto v = *st.begin(); st.erase(st.begin()); for(auto it : g[v.S.F][v.S.S]){ if(ans[l][r][it.F][it.S] > ans[l][r][v.S.F][v.S.S] + 1){ st.erase({ans[l][r][it.F][it.S] , {it.F , it.S}}); ans[l][r][it.F][it.S] = ans[l][r][v.S.F][v.S.S] + 1; st.insert({ans[l][r][it.F][it.S] , {it.F , it.S}}); } } } } } int mx = inf; for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)mx = min(mx , ans[1][n][i][j]); cout << mx; } signed main(){ int t = 1; Bekabot while(t--)skibidi_dop_dop_dop_yes_yes(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...