| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 846538 |
2023-09-07T19:14:53 Z |
Saacoota |
Robots (APIO13_robots) |
C++14 |
|
1500 ms |
8536 KB |
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
#define LL unsigned long long
#define uint unsigned int
#define pb push_back
#define eb emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "AROBOT"
using namespace std;
const int oo = 1e9 + 5;
int n , m , r;
int dp[10][10][502][502];
ii null , f[502][502][4];
bool vs[502][502];
string s[502];
int dx[] = { 0 , -1 , 0 , 1};
int dy[] = { 1 , 0 , -1 , 0};
///--------------------------
ii F(int x,int y,int direct) {
if (f[x][y][direct] != null) return f[x][y][direct];
ii &res = f[x][y][direct];
if (vs[x][y]) {
res = ii(x,y);
return res;
}
vs[x][y] = true;
if (s[x][y] != 'A' && s[x][y] != 'C') {
int nx = x + dx[direct] , ny = y + dy[direct];
if (nx < 1 || nx > m || ny < 1 || ny > n || s[nx][ny] == 'x') res = ii(x , y);
else res = F(nx , ny , direct);
} else {
int ndirect = direct;
if (s[x][y] == 'A') ndirect++;
else ndirect--;
ndirect = (ndirect + 4) % 4;
int nx = x + dx[ndirect] , ny = y + dy[ndirect];
if (nx < 1 || nx > m || ny < 1 || ny > n || s[nx][ny] == 'x') res = ii(x , y);
else res = F(nx , ny , ndirect);
}
vs[x][y] = false;
return res;
}
///--------------------------
void readf() {
cin >> r >> n >> m ;
for (int i = 1 ; i <= m ; ++i) {
cin >> s[i];
s[i] = " " + s[i];
}
}
///--------------------------
void solve() {
null = ii(0,0);
for (int i = 1 ; i <= r ; ++i)
for (int j = 1 ; j <= r ; ++j)
for (int x = 1 ; x <= m ; ++x)
for (int y = 1 ; y <= n ; ++y) dp[i][j][x][y] = oo;
for (int i = 1 ; i <= m ; ++i)
for (int j = 1 ; j <= n ; ++j) {
if (s[i][j] != 'x') {
for (int k = 0 ; k < 4 ; ++k)
if (f[i][j][k] == null) f[i][j][k] = F(i , j , k);
}
if ('1' <= s[i][j] && s[i][j] <= '9') dp[s[i][j] - '0'][s[i][j] - '0'][i][j] = 0;
}
for (int i = r ; i > 0 ; ++i)
for (int j = i ; j <= r ; ++j) {
vector < iii2 > wa;
for (int x = 1 ; x <= m ; ++x)
for (int y = 1 ; y <= n ; ++y) {
for (int k = i ; k < j ; ++k)
dp[i][j][x][y] = min(dp[i][j][x][y] , dp[i][k][x][y] + dp[k+1][j][x][y]);
if (dp[i][j][x][y] < oo) {
wa.pb({dp[i][j][x][y] , {x , y}});
}
}
stack < iii2 > stk , pa;
sort(wa.rbegin(),wa.rend());
for (auto x : wa) stk.push(x);
while (!stk.empty()) {
int val = stk.top().fi;
while (!stk.empty() && stk.top().fi == val) {
pa.push(stk.top());
stk.pop();
}
while (!pa.empty()) {
int x = pa.top().se.fi , y = pa.top().se.se;
pa.pop();
for (int k = 0 ; k < 4 ; ++k) {
int nx = f[x][y][k].fi , ny = f[x][y][k].se;
if (nx == x && ny == y) continue;
if (dp[i][j][nx][ny] > val + 1) {
dp[i][j][nx][ny] = val + 1;
stk.push({val + 1 , f[x][y][k]});
}
}
}
}
}
int ans = oo;
for (int i = 1 ; i <= m ; ++i)
for (int j = 1 ; j <= n ; ++j) ans = min(ans , dp[1][r][i][j]);
if (ans < oo) cout << ans;
else cout << -1;
}
///--------------------------
main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
readf();
solve();
}
Compilation message
robots.cpp:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
115 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
8536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
8536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
8536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1576 ms |
8536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
