| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122396 |
2019-06-28T07:01:53 Z |
김세빈(#2988) |
Robots (APIO13_robots) |
C++14 |
|
14 ms |
14720 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
vector <int> V[303030], X[303030];
queue <pii> Q;
char S[555][555];
int chk[555][555][4];
int vis[303030];
int dp[303030][55];
int _N[10][10], _X[55], _Y[55];
int n, m, k, cnt, ans;
int dfs(int x, int y, int d)
{
if(chk[x][y][d] >= 0) return chk[x][y][d];
else if(chk[x][y][d] == -1) return -1;
chk[x][y][d] = -1;
int ret, _d;
if(S[x][y] == 'A') _d = (d + 1) % 4;
else if(S[x][y] == 'C') _d = (d + 3) % 4;
else _d = d;
if(_d == 0){
if(x == n - 1 || S[x + 1][y] == 'x') ret = x * m + y;
else ret = dfs(x + 1, y, _d);
}
else if(_d == 1){
if(y == m - 1 || S[x][y + 1] == 'x') ret = x * m + y;
else ret = dfs(x, y + 1, _d);
}
else if(_d == 2){
if(x == 0 || S[x - 1][y] == 'x') ret = x * m + y;
else ret = dfs(x - 1, y, _d);
}
else{
if(y == 0 || S[x][y - 1] == 'x') ret = x * m + y;
else ret = dfs(x, y - 1, _d);
}
return chk[x][y][d] = ret;
}
int main()
{
int i, j, l, s;
scanf("%d%d%d", &k, &m, &n);
s = 0;
for(i=1; i<=k; i++){
for(j=i; j>=1; j--){
_N[i][j] = s;
_X[s] = i; _Y[s] = j;
s ++;
}
}
for(i=0; i<n; i++){
scanf("%s", S[i]);
for(j=0; j<m; j++){
for(l=0; l<4; l++){
chk[i][j][l] = -2;
}
for(l=0; l<k*(k+1)/2; l++){
dp[i * m + j][l] = 1e9;
}
if('1' <= S[i][j] && S[i][j] <= '0' + k){
dp[i * m + j][(int)(S[i][j] - '0') * (S[i][j] - '0' - 1) / 2] = 0;
}
}
}
for(i=0; i<n; i++){
for(j=0; j<m; j++){
for(l=0; l<4; l++){
if(dfs(i, j, l) != -1 && dfs(i, j, l) != i * m + j){
V[i * m + j].push_back(dfs(i, j, l));
}
}
}
}
for(i=0; i<k*(k+1)/2; i++){
int v = 1e9;
for(j=0; j<n; j++){
for(l=0; l<m; l++){
v = min(v, dp[j * m + l][i]);
}
}
if(v == 1e9) continue;
for(j=0; j<n; j++){
for(l=0; l<m; l++){
if(dp[j * m + l][i] < v + n * m){
X[dp[j * m + l][i] - v].push_back(j * m + l);
}
}
}
cnt ++; for(; !Q.empty(); Q.pop());
for(j=0; j<n*m; j++){
for(int &t: X[j]) if(vis[t] != cnt){
vis[t] = cnt;
Q.push(pii(t, j));
}
X[j].clear();
for(; !Q.empty() && Q.front().second == j;){
int p = Q.front().first; Q.pop();
dp[p][i] = j + v;
for(int &t: V[p]) if(vis[t] != cnt){
Q.push(pii(t, j + 1));
vis[t] = cnt;
}
}
}
int x = _X[i], y = _Y[i], z;
for(j=0; j<n; j++){
for(l=0; l<m; l++){
int id = j * m + l;
for(z=y-1; z>=1; z--){
dp[id][_N[x][z]] = min(dp[id][_N[x][z]], dp[id][_N[y - 1][z]] + dp[id][i]);
}
}
}
/*
printf("%d %d\n", y, x);
for(j=0; j<n; j++){
for(l=0; l<m; l++){
if(dp[j * m + l][i] == 1e9) printf(" X");
else printf("%3d", dp[j * m + l][i]);
}
printf("\n");
}
printf("\n");
*/ }
ans = 1e9;
for(i=0; i<n; i++){
for(j=0; j<m; j++){
ans = min(ans, dp[i * m + j][k * (k + 1) / 2 - 1]);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &k, &m, &n);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", S[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
14720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
14720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
14720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
14720 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
