제출 #541303

#제출 시각아이디문제언어결과실행 시간메모리
541303jiahng로봇 (APIO13_robots)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define ll int //~ #define int ll typedef pair<ll, ll> pi; typedef vector <int> vi; typedef vector <pi> vpi; typedef pair<pi, ll> pii; typedef set <ll> si; typedef long double ld; #define f first #define s second #define mp make_pair #define FOR(i,s,e) for(int i=s;i<=int(e);++i) #define DEC(i,s,e) for(int i=s;i>=int(e);--i) #define pb push_back #define all(x) (x).begin(), (x).end() #define lbd(x, y) lower_bound(all(x), y) #define ubd(x, y) upper_bound(all(x), y) #define aFOR(i,x) for (auto i: x) #define mem(x,i) memset(x,i,sizeof x) #define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define maxh 11 #define maxn 3 #define INF 1e9 #define MOD 998244353 typedef pair <vi, int> pvi; typedef pair <int,pi> ipi; int N,H,W; char A[maxh][maxh]; pi dp[maxh][maxh][4]; //~ int vis[maxh][maxh][4]; int dr[] = {-1,0,1,0}; //clockwise from up int dc[] = {0,1,0,-1}; pi dfs(int i,int j,int k){ //~ cout << i << ' ' << j << ' ' << k << '\n'; if (dp[i][j][k] == pi(0,0)){ //~ assert(0); return dp[i][j][k] = pi(-1,-2); } if (dp[i][j][k] != pi(-1,-1)) return dp[i][j][k]; dp[i][j][k] = pi(0,0); int nk = k; if (A[i][j] == 'A') (nk+=3) %= 4; if (A[i][j] == 'C') (nk+=1) %= 4; int nr = i + dr[nk]; int nc = j + dc[nk]; if (nr < 1 || nr > H || nc < 1 || nc > W || A[nr][nc] == 'x') dp[i][j][k] = pi(i,j); else dp[i][j][k] = dfs(nr, nc, nk); return dp[i][j][k]; //~ if (vis[i][j][k] == 2) return dp[i][j][k]; //~ if (vis[i][j][k] == 1){ //~ return dp[i][j][k] = pi(-1,-1); //~ } //~ vis[i][j][k] = 1; //~ int nk = k; //~ if (A[i][j] == 'A') (nk+=3) %= 4; //~ if (A[i][j] == 'C') (nk+=1) %= 4; //~ int nr = i + dr[nk]; //~ int nc = j + dc[nk]; //~ if (nr < 1 || nr > H || nc < 1 || nc > W || A[nr][nc] == 'x') dp[i][j][k] = pi(i,j); //~ else dp[i][j][k] = dfs(nr, nc, nk); //~ vis[i][j][k] = 2; //~ return dp[i][j][k]; } int dp2[maxn][maxn][maxh][maxh]; queue <pi> Q[maxh*maxh]; int32_t main(){ fast; cin >> N >> W >> H; FOR(i,1,H) FOR(j,1,W) cin >> A[i][j]; // find where each (i,j,k) goes to FOR(i,1,H) FOR(j,1,W) FOR(k,0,3) dp[i][j][k] = pi(-1,-1); FOR(i,1,H) FOR(j,1,W) FOR(k,0,3) if (dp[i][j][k] == pi(-1,-1)) dfs(i,j,k); //~ cout << dp[1][1][2].f << ' ' << dp[1][1][2].s; //~ return 0; FOR(l,1,N) FOR(a,1,N){ int b = a + l - 1; if (b > N) continue; FOR(x,1,H) FOR(y,1,W){ dp2[a][b][x][y] = INF; FOR(c, a, b-1) dp2[a][b][x][y] = min( dp2[a][b][x][y], dp2[a][c][x][y] + dp2[c+1][b][x][y]); if (a == b && A[x][y] == a + '0') dp2[a][b][x][y] = 0; } FOR(x,1,H) FOR(y,1,W) if (dp2[a][b][x][y] <= H * W) Q[dp2[a][b][x][y]].push(pi(x,y)); //~ FOR(x,1,H) FOR(y,1,W) dist[x][y] = -1; FOR(d,0,H*W){ while (!Q[d].empty()){ pi cur = Q[d].front(); Q[d].pop(); //~ cerr << a << ' ' << b << ' ' << cur.f << ' ' << cur.s << '\n'; if (dp2[a][b][cur.f][cur.s] < d) continue; dp2[a][b][cur.f][cur.s] = d; FOR(k,0,3) if (dp[cur.f][cur.s][k].f != -1){ Q[d+1].push(dp[cur.f][cur.s][k]); } //~ aFOR(x, adj[cur.f][cur.s]){ //~ if (dist[x.f][x.s] == -1) Q[d+1].push(x); //~ } } } //~ FOR(x,1,H) FOR(y,1,W) dp2[a][b][x][y] = (dist[x][y] == -1 ? INF : dist[x][y]); } //~ aFOR(i,adj[5][5]) cout << i.f << ' ' << i.s << '\n'; //~ return 0; //~ cout << dp2[2][2][5][5]; //~ return 0; int ans = INF; FOR(i,1,H) FOR(j,1,W) ans = min(ans, dp2[1][N][i][j]); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...