#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 500;
const int INF = 987654321;
const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};
const int dA[]={2, 3, 1, 0};
const int dC[]={3, 2, 0, 1};
int N, W, H;
char A[MAXN+10][MAXN+10];
pii dest[MAXN+10][MAXN+10][4];
int dp[MAXN+10][MAXN+10][10][10];
void dfs(int y, int x, int dir)
{
if(dest[y][x][dir]!=pii(-1, -1)) return;
int ndir;
if(A[y][x]=='A') ndir=dA[dir];
else if(A[y][x]=='C') ndir=dC[dir];
else ndir=dir;
int ny=y+dy[ndir], nx=x+dx[ndir];
if(A[ny][nx]=='x')
{
dest[y][x][dir]={y, x};
return;
}
dfs(ny, nx, ndir);
dest[y][x][dir]=dest[ny][nx][ndir];
}
struct Queue
{
int y, x, w;
bool operator < (const Queue &p) const { return w>p.w; }
};
int main()
{
int i, j, k, p, q;
scanf("%d%d%d", &N, &W, &H);
for(i=1; i<=H; i++) scanf("%s", A[i]+1);
for(i=0; i<=H+1; i++) A[i][0]=A[i][W+1]='x';
for(j=0; j<=W+1; j++) A[0][j]=A[H+1][j]='x';
for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++) dest[i][j][k]={-1, -1};
for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++)
{
if(dest[i][j][k]!=pii(-1, -1)) continue;
dfs(i, j, k);
}
//for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("(%d %d / %d %d / %d %d / %d %d) ", dest[i][j][0].first, dest[i][j][0].second, dest[i][j][1].first, dest[i][j][1].second, dest[i][j][2].first, dest[i][j][2].second, dest[i][j][3].first, dest[i][j][3].second); printf("\n"); }
for(q=1; q<=N; q++) for(p=q; p>=1; p--)
{
priority_queue<Queue> PQ;
for(i=1; i<=H; i++) for(j=1; j<=W; j++) dp[i][j][p][q]=INF;
if(p==q)
{
for(i=1; i<=H; i++) for(j=1; j<=W; j++)
{
int now;
if(A[i][j]=='0'+p) now=0;
else now=INF;
PQ.push({i, j, now});
}
}
else
{
for(i=1; i<=H; i++) for(j=1; j<=W; j++)
{
int now=INF;
for(k=p; k<q; k++)
{
now=min(now, dp[i][j][p][k]+dp[i][j][k+1][q]);
}
PQ.push({i, j, now});
}
}
while(!PQ.empty())
{
Queue T=PQ.top(); PQ.pop();
//printf("!%d %d %d\n", T.x, T.y, T.w);
if(dp[T.y][T.x][p][q]<=T.w) continue;
dp[T.y][T.x][p][q]=T.w;
// if(dp[dest[T.y][T.x][k].first][dest[T.y][T.x][k].second][p][q]>T.w+1)
for(k=0; k<4; k++) PQ.push({dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, T.w+1}); //printf("?%d %d %d\n", dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, T.w+1);
}
//printf("=======%d %d========\n", p, q);
//for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("%d ", dp[i][j][p][q]); printf("\n"); }
}
int ans=INF;
for(i=1; i<=H; i++) for(j=1; j<=W; j++) ans=min(ans, dp[i][j][1][N]);
if(ans==INF) printf("?1");
else printf("%d", ans);
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &W, &H);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=H; i++) scanf("%s", A[i]+1);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
