#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;
//using hasing, O(W*H*N^3);
const int MV = 502*502;
const int ME = 502*502*4*2; //~=2,000,000;
const int INF = 1e8;
struct point{
point(){}
point(int x,int y):x(x),y(y){}
int x,y;
int value(){return 500*(x-1)+y;}
}inp[10];
int n,w,h;
int xx[4]={-1,0,1,0}, yy[4]={0,1,0,-1};
char ch[510][510];
bool wall[510][510];
bool m_check[4][510][510]; //using in function make_edge;
bool A[510][510],C[510][510];
bool check[MV]; //using in function Merge;
int Q[MV][2]; //0:depth, 1:tr of point;
short b_check[MV]; //using in function BFS; assigned by 1~9;
int Dp[9][9][502][502];
typedef pair<int,int> P;
vector <point> has;
int st[MV],en[ME];
int next[ME];
int c_edge;
vector <int> Hash[2500020];
inline int tr(int x,int y){return 500*(x-1)+y;}
P itr(int x){return P((x-1)/500+1,(x-1)%500+1);}
void addedge(int s,int d)
{
++c_edge;
next[c_edge]=st[s];
st[s]=c_edge;
en[c_edge]=d;
}
void make_edge()
{
int i,j,k;
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
for(k=0;k<4;k++){
if(wall[i+xx[k^2]][j+yy[k^2]])continue;
int ink = k;
int tx = i, ty = j;
if(A[i][j])ink=(ink+1)%4;
else if(C[i][j])ink=(ink?ink-1:3);
while(!m_check[ink][tx][ty] && wall[tx][ty]){
//printf("%d %d -> %d %d\n",tx,ty,i,j);
addedge(tr(tx,ty),tr(i,j));
m_check[ink][tx][ty]=1;
tx+=xx[ink];
ty+=yy[ink];
if(A[tx][ty])ink=(ink+1)%4;
else if(C[tx][ty])ink=(ink?ink-1:3);
}
}
}
}
}
void BFS(int x)
{
int fr=1,re=0;
int vx = inp[x].value();
Q[0][0]=vx,Q[0][1]=0;
b_check[vx]=x+1;
while(fr!=re){
int i;
int tx = Q[re][0];
for(i=st[tx];i;i=next[i]){
if(b_check[en[i]] == x+1)continue;
b_check[en[i]]=x+1;
Q[fr][0]=en[i];
Q[fr][1]=Q[re][1]+1;
fr++;
}
P tmp = itr(Q[re][0]);
Dp[x][x][tmp.first][tmp.second]=Q[re++][1];
}
}
void Init()
{
int i,j,k;
for(i=0;i<n;i++){
for(j=1;j<=h;j++){
for(k=1;k<=w;k++){
if(inp[i].x==j && inp[i].y==k)continue;
if(!Dp[i][i][j][k])Dp[i][i][j][k] = INF;
}
}
}
}
void Merge(int a,int b,int c)
{
//assigning Dp[a][c] with Dp[a][b] & Dp[b+1][c];
memset(check,0,sizeof(check));
int max_num=0;
int i,j;
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
if(Dp[a][b][i][j]==INF || Dp[b+1][c][i][j]==INF)continue;
int tmp = tr(i,j);
int tmp2 = Dp[a][b][i][j]+Dp[b+1][c][i][j];
Hash[tmp2].push_back(tmp);
max_num = max(max_num,tmp2);
}
}
for(i=1;i<=max_num;i++){
if(Hash[i].empty())continue;
for(j=0;j<Hash[i].size();j++){
if(check[Hash[i][j]])continue;
check[Hash[i][j]]=1;
P tmp = itr(Hash[i][j]);
Dp[a][c][tmp.first][tmp.second]=min(Dp[a][c][tmp.first][tmp.second],i);
for(int k=st[Hash[i][j]];k;k=next[k]){
if(check[en[k]])continue;
Hash[i+1].push_back(en[k]);
max_num=max(max_num,i+1);
}
}
Hash[i].clear();
}
}
void output()
{
int i,j,ans=INF;
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
ans=min(ans,Dp[0][n-1][i][j]);
}
}
printf("%d",ans==INF?-1:ans);
}
void init(int x,int y)
{
int i,j;
for(i=1;i<=h;i++){
for(j=1;j<=w;j++)Dp[x][y][i][j]=INF;
}
}
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d%d%d",&n,&w,&h);
int i,j,k;
for(i=1;i<=h;i++){
scanf("%s",ch[i]+1);
for(j=1;j<=w;j++){
if(ch[i][j]!='x')wall[i][j]=1;
if(ch[i][j]<='9'&&ch[i][j]>='1')inp[ch[i][j]-'1']=point(i,j);
if(ch[i][j]=='A')A[i][j]=1;
else if(ch[i][j]=='C')C[i][j]=1;
}
}
make_edge();
for(i=0;i<n;i++)BFS(i);
Init();
for(i=1;i<n;i++){
for(j=0;j<n-i;j++){
//assigning Dp[j][j+i];
init(j,j+i);
for(k=0;k<i;k++){
//Dp[j][j+i] = Dp[j][j+k]+Dp[j+k+1][j+i];
Merge(j,j+k,j+i);
}
}
}
output();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
161012 KB |
Output is correct |
| 2 |
Correct |
12 ms |
161012 KB |
Output is correct |
| 3 |
Correct |
8 ms |
161012 KB |
Output is correct |
| 4 |
Correct |
8 ms |
161012 KB |
Output is correct |
| 5 |
Correct |
16 ms |
161012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
161012 KB |
Output is correct |
| 2 |
Correct |
8 ms |
161012 KB |
Output is correct |
| 3 |
Correct |
12 ms |
161012 KB |
Output is correct |
| 4 |
Correct |
8 ms |
161012 KB |
Output is correct |
| 5 |
Correct |
16 ms |
161012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
72 ms |
163840 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
