#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
const int N = 505;
char a[N][N];
bool seen[5][N][N];
int x[N];
int y[N];
pair<int,int> tar[5][N][N];
int mn[100][N][N];
map<int,pair<int,int>> d;
map<pair<char,int>,int> chd;
int n,m;
bool valid(int i,int j,int cur){
if (min(i,j) < 1 or i>n or j>m or a[i][j]=='x')
return false;
return true;
}
int dfs(int i,int j,int cur){
if (a[i][j] == 'A' or a[i][j] == 'C')
cur = chd[{a[i][j],cur}];
seen[cur][i][j] = true;
int ni = i + d[cur].first;
int nj = j + d[cur].second;
int ncur = cur;
if (a[ni][nj] == 'A' or a[ni][nj] == 'C')
ncur = chd[{a[ni][nj],cur}];
if (seen[ncur][ni][nj]){
tar[cur][i][j] = tar[ncur][ni][nj];
return cur;
}
if (!valid(ni,nj,cur)){
tar[cur][i][j] = {i,j};
return cur;
}
ncur = dfs(ni,nj,cur);
tar[cur][i][j] = tar[ncur][ni][nj];
return cur;
}
// up 1
// left 2
// down 3
// right 4
void bfs(int ii,int jj,int cur,int init = 0){
set<vector<int>> s;
s.insert({init,ii,jj});
mn[cur][ii][jj] = init;
while (s.size()>0){
vector<int> v = *begin(s);
s.erase(begin(s));
// if (cur/10 != cur%10)
// cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;
for (int i = 1;i<=4;i++){
auto [ni,nj] = tar[i][v[1]][v[2]];
if (ni == -1)
continue;
if (mn[cur][ni][nj] <= v[0])
continue;
mn[cur][ni][nj] = v[0] + 1;
s.insert({v[0] + 1,ni,nj});
}
}
}
int main(){
chd[{'A',1}] = 2;
chd[{'A',2}] = 3;
chd[{'A',3}] = 4;
chd[{'A',4}] = 1;
chd[{'C',2}] = 1;
chd[{'C',3}] = 2;
chd[{'C',4}] = 3;
chd[{'C',1}] = 4;
d[1] = {-1,0};
d[2] = {0,-1};
d[4] = {0,1};
d[3] = {1,0};
int k;
cin>>k>>m>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
cin>>a[i][j];
int c = a[i][j] - 48;
if (isdigit(a[i][j]))
x[c] = i,y[c] = j;
}
for (int cur=1;cur<=4;cur++)
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
tar[cur][i][j] = {-1,-1};
for (int cur=1;cur<=4;cur++)
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!seen[cur][i][j])
dfs(i,j,cur);
// for (int i = 1;i<=4;i++){
// auto [ni,nj] = tar[i][4][1];
// cout<<ni<<" "<<nj<<endl;
// }
// return 0;
for (int cur=1;cur<100;cur++)
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
mn[cur][i][j] = 1e8;
for (int i=1;i<=k;i++){
// cout<<endl<<i<<i<<" "<<x[i]<<" "<<y[i]<<" "<<endl;
bfs(x[i],y[i],i * 10 + i);
}
for (int i=k;i>=1;i--){
for (int j=i+1;j<=k;j++){
int Mn = 1e8;
int row = -1,col = -1;
for (int l=i;l<j;l++){
for (int r=1;r<=n;r++){
for (int c=1;c<=m;c++){
int f = i * 10 + l;
int s = (l + 1) * 10 + j;
// if (i==3 and j==4)
// cout<<"fghjhgfdfghj "<<f<<" "<<s<<" "<<r<<" "<<c<<" "<<mn[f][r][c] + mn[s][r][c]<<endl;
if (mn[f][r][c] + mn[s][r][c] < Mn)
Mn = mn[f][r][c] + mn[s][r][c],row = r,col = c;
}// for c
} // for r
}// for l
if (row != -1){
// cout<<endl<<i<<j<<" "<<Mn<<" "<<row<<" "<<col<<endl;
bfs(row,col,i * 10 + j,Mn);
}
}// for j
} // for i
int ans = 1e7;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
ans = min(ans,mn[10 + k][i][j]);
if (ans == 1e7)
ans = -1;
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
111196 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
111216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
111196 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
111216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
111196 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
111216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
111196 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
111216 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
