| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 364480 |
2021-02-09T10:11:42 Z |
AriaH |
Robots (APIO13_robots) |
C++11 |
|
80 ms |
124524 KB |
/** Im the best because i work as hard as i possibly can **/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl "\n"
const int N = 5e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 5e8;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
char C[N];
string S[N];
int n, m, k, mark[N][N], dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}, dp[11][11][N][N], dis[N][N];
pii f[4][N][N], emp = {0, 0};
pii dfs(int d, int x, int y)
{
if(f[d][x][y] != emp) return f[d][x][y];
pii &cu = f[d][x][y];
if(mark[x][y]) return cu = Mp(x, y);
mark[x][y] = 1;
if(S[x][y] == 'A' || S[x][y] == 'C')
{
int d2 = d + (S[x][y] == 'A'? 1 : -1);
d2 = (d2 + 4) % 4;
int x2 = x + dx[d2], y2 = y + dy[d2];
if(S[x2][y2] == '#') cu = Mp(x, y);
else cu = dfs(d2, x2, y2);
}
else
{
int x2 = x + dx[d], y2 = y + dy[d];
if(S[x2][y2] == '#') cu = Mp(x, y);
else cu = dfs(d, x2, y2);
}
mark[x][y] = 0;
return cu;
}
int main()
{
scanf("%d%d%d", &k, &m, &n);
for(int i = 1; i <= n; i ++)
{
scanf("%s", C);
S[i] = C;
S[i] = "#" + S[i] + "#";
}
for(int j = 0; j <= m; j ++) S[0][j] = S[n + 1][j] = '#';
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if(S[i][j] != '#')
{
for(int d = 0; d < 4; d ++)
{
f[d][i][j] = dfs(d, i, j);
}
}
}
}
for(int i = 0; i < 11; i ++)
{
for(int j = 0; j < 11; j ++)
{
for(int K = 0; K < N; K ++)
{
for(int t = 0; t < N; t ++)
{
dp[i][j][K][t] = inf;
}
}
}
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
if('1' <= S[i][j] && S[i][j] <= '9')
{
dp[S[i][j] - '0'][S[i][j] - '0'][i][j] = 0;
}
}
}
/*
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
printf("i = %d j = %d : %d %d %d %d %d %d %d %d\n", i, j, f[0][i][j].F, f[0][i][j].S, f[1][i][j].F, f[1][i][j].S, f[2][i][j].F, f[2][i][j].S, f[3][i][j].F, f[3][i][j].S);
}
}
*/
for(int tool = 1; tool <= k; tool ++)
{
for(int l = 1; l <= k - tool + 1; l ++)
{
set < pair < int, pii > > st;
for(int i = 0; i < N; i ++)
{
for(int j = 0; j < N; j ++)
{
dis[i][j] = inf;
}
}
int r = l + tool - 1;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
for(int mid = l; mid < r; mid ++)
{
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][mid][i][j] + dp[mid + 1][r][i][j]);
}
dis[i][j] = dp[l][r][i][j];
if(dis[i][j] < inf) st.insert(Mp(dis[i][j], Mp(i, j)));
}
}
while(!st.empty())
{
pair < int, pii > cu = *st.begin();
int x = cu.S.F, y = cu.S.S;
st.erase(st.begin());
for(int d = 0; d < 4; d ++)
{
pii now = f[d][x][y];
if(S[now.F][now.S] == '#' || now == emp) continue;
if(dis[now.F][now.S] > dis[x][y] + 1)
{
dis[now.F][now.S] = dis[x][y] + 1;
st.insert(Mp(dis[now.F][now.S], now));
}
}
}
for(int i = 0; i < N; i ++)
{
for(int j = 0; j < N; j ++)
{
dp[l][r][i][j] = dis[i][j];
}
}
}
}
int tot = inf;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
tot = min(tot, dp[1][k][i][j]);
}
}
if(tot >= inf) tot = -1;
printf("%d\n", tot);
return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | scanf("%d%d%d", &k, &m, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | scanf("%s", C);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
124524 KB |
Output is correct |
| 2 |
Incorrect |
80 ms |
124524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
124524 KB |
Output is correct |
| 2 |
Incorrect |
80 ms |
124524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
124524 KB |
Output is correct |
| 2 |
Incorrect |
80 ms |
124524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
124524 KB |
Output is correct |
| 2 |
Incorrect |
80 ms |
124524 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
