#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int N=505;
const int K=12;
const int oo=1e9+1;
int n,m,k,dist,l,r,u,v,x,y,SAVE_L,SAVE_R,d[K][K][N][N];
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
int A[]={1,3,0,2},C[]={2,0,3,1};
pii nxt[N][N][5];
bool visited[N][N][5];
char s[N][N];
vector <pii> ve;
deque <pii> dq;
pii dfs(int u,int v,int dir)
{
if (s[u][v]=='A') dir=A[dir];
if (s[u][v]=='C') dir=C[dir];
if (nxt[u][v][dir]!=make_pair(0,0)) return nxt[u][v][dir];
if (visited[u][v][dir]) return nxt[u][v][dir]=make_pair(-1,-1);
visited[u][v][dir]=true;
if (s[u+dx[dir]][v+dy[dir]]=='x') return nxt[u][v][dir]=make_pair(u,v);
return nxt[u][v][dir]=dfs(u+dx[dir],v+dy[dir],dir);
}
bool cmp(pii a,pii b)
{
return d[SAVE_L][SAVE_R][a.X][a.Y]>d[SAVE_L][SAVE_R][b.X][b.Y];
}
int dial()
{
for (int l=k;l>=1;l--)
for (int r=l;r<=n;r++)
{
ve.clear();
for (int x=1;x<=n;x++)
for (int y=1;y<=m;y++)
if (d[l][r][x][y]!=oo) ve.push_back(make_pair(x,y));
SAVE_L=l;
SAVE_R=r;
sort(ve.begin(),ve.end(),cmp);
if (!ve.empty() and l==1 and r==k)
return d[l][r][ve.back().X][ve.back().Y];
while (!dq.empty() or !ve.empty())
{
if (dq.empty())
{
dq.push_back(ve.back());
ve.pop_back();
}
while (!dq.empty())
{
u=dq.front().X;
v=dq.front().Y;
dq.pop_front();
dist=d[l][r][u][v];
while (!ve.empty() and d[l][r][ve.back().X][ve.back().Y]==dist)
{
dq.push_front(ve.back());
ve.pop_back();
}
for (int i=l-1;i>=1;i--)
d[i][r][u][v]=min(d[i][r][u][v],d[l][r][u][v]+d[i][l-1][u][v]);
for (int j=r+1;j<=k;j++)
d[l][j][u][v]=min(d[l][j][u][v],d[l][r][u][v]+d[r+1][j][u][v]);
for (int dir=0;dir<=3;dir++)
if (nxt[u][v][dir]!=make_pair(-1,-1))
{
x=nxt[u][v][dir].X;
y=nxt[u][v][dir].Y;
if (d[l][r][x][y]>dist+1)
{
d[l][r][x][y]=dist+1;
dq.push_back(make_pair(x,y));
}
}
}
}
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL); cout.tie(NULL);
cin >> k >> m >> n;
for (int i=0;i<=n+1;i++)
s[i][0]=s[i][m+1]='x';
for (int j=0;j<=m+1;j++)
s[0][j]=s[n+1][j]='x';
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin >> s[i][j];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int dir=0;dir<=3;dir++)
if (s[i][j]!='x') dfs(i,j,dir);
for (int l=1;l<=k;l++)
for (int r=l;r<=k;r++)
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
d[l][r][i][j]=oo;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (s[i][j]>'0' and s[i][j]<=k+'0')
{
int id=s[i][j]-'0';
d[id][id][i][j]=0;
}
cout << dial();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |