#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf=1e9;
int dp[10][10][505][505];
char c[505][505];
vector<ii> dist[500*500+5];
bool vis[505][505];
vector<ii> AdjList[505][505];
int n,h,w;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool ok(int x, int y) {
return x>=1&&x<=h&&y>=1&&y<=w&&c[x][y]!='x';
}
int id(int x, int y) {
return (x-1)*w+y;
}
ii run(int x, int y, int id) {
//cout<<"go "<<x<<" "<<y<<" "<<id<<endl;
while(true) {
//cout<<x<<" "<<y<<endl;
if(c[x][y]=='C') id=(id+1)%4;
if(c[x][y]=='A') id=(id+3)%4;
int nx=x+dx[id];
int ny=y+dy[id];
if(!ok(nx,ny)) return ii(x,y);
x=nx; y=ny;
}
}
void bfs(int l, int r) {
//cout<<"bfs "<<l<<" "<<r<<endl;
for(int i=1 ; i<=h ; i++) {
for(int j=1 ; j<=w ; j++) {
vis[i][j]=0;
}
}
for(int i=0 ; i<=n*n ; i++) {
dist[i].clear();
}
int mn=inf;
for(int i=1 ; i<=h ; i++) {
for(int j=1 ; j<=w ; j++) {
if(dp[l][r][i][j]!=-1) {
//cout<<"dp "<<l<<" "<<r<<" "<<i<<" "<<j<<" = "<<dp[l][r][i][j]<<endl;
dist[dp[l][r][i][j]].push_back(ii(i,j));
mn=min(dp[l][r][i][j],mn);
}
}
}
queue<ii> q;
while(!dist[mn].empty()) {
q.push(dist[mn].back());
dist[mn].pop_back();
}
while(!q.empty()) {
ii tmp=q.front();
q.pop();
int x=tmp.first;
int y=tmp.second;
//cout<<"dp "<<l<<" "<<r<<" "<<x<<" "<<y<<" = "<<dp[l][r][x][y]<<endl;
if(vis[x][y]) continue;
vis[x][y]=1;
while(!dist[dp[l][r][x][y]].empty()) {
q.push(dist[dp[l][r][x][y]].back());
dist[dp[l][r][x][y]].pop_back();
}
for(ii tmp1: AdjList[x][y]) {
int nx=tmp1.first; int ny=tmp1.second;
//cout<<"nx ny = "<<nx<<" "<<ny<<endl;
if(dp[l][r][nx][ny]>dp[l][r][x][y]+1||dp[l][r][nx][ny]==-1) {
q.push(ii(nx,ny));
dp[l][r][nx][ny]=dp[l][r][x][y]+1;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
cin>>w>>h;
memset(dp,-1,sizeof(dp));
for(int i=1 ; i<=h ; i++) {
cin>>c[i]+1;
for(int j=1 ; j<=w ; j++) {
if(c[i][j]>='0'&&c[i][j]<='9') {
int x=c[i][j]-'0';
dp[x][x][i][j]=0;
}
}
}
for(int i=1 ; i<=h ; i++) {
for(int j=1 ; j<=w ; j++) {
for(int id=0 ; id<4 ; id++) {
AdjList[i][j].push_back(run(i,j,id));
}
}
}
for(int d=0 ; d<n ; d++) {
for(int l=1 ; l+d<=n ; l++) {
int r=l+d;
for(int mid=l ; mid<r ; mid++) {
for(int x=1 ; x<=h ; x++) {
for(int y=1 ; y<=w ; y++) {
if((dp[l][r][x][y]==-1||dp[l][r][x][y]>dp[l][mid][x][y]+dp[mid+1][r][x][y])&&(dp[l][mid][x][y]!=-1&&dp[mid+1][r][x][y]!=-1))
dp[l][r][x][y]=dp[l][mid][x][y]+dp[mid+1][r][x][y];
}
}
}
bfs(l,r);
}
}
int ans=inf;
for(int i=1 ; i<=h ; i++) {
for(int j=1 ; j<=w ; j++) {
if(dp[1][n][i][j]!=-1) ans=min(ans,dp[1][n][i][j]);
}
}
if(ans==inf) cout<<-1;
else cout<<ans;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | cin>>c[i]+1;
| ~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
111952 KB |
Output is correct |
| 2 |
Runtime error |
155 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
111952 KB |
Output is correct |
| 2 |
Runtime error |
155 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
111952 KB |
Output is correct |
| 2 |
Runtime error |
155 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
111952 KB |
Output is correct |
| 2 |
Runtime error |
155 ms |
163840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
