#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=5e2;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,t,num,e,q,w,h;
int dx[8]={-1,0,1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
char c;
string s;
int a[LIM+5],factorial[(1<<maxn)+5],inv_fact[(1<<maxn)+5];
int dp[10][10][LIM+5][LIM+5];
vector<pii> memodfs[LIM+5][LIM+5];
bool vis[LIM+5][LIM+5];
bool notprime[LIM+5];
vector<pii> dist[LIM*LIM+5];
map<int,int> mp;
char grid[LIM+5][LIM+5];
int power(int a,int b){
if(b==0) return 1;
int t=power(a,b/2);
t = t * t %mod;
if(b%2==1) t = t * a %mod;
return t;
}
bool check(int x,int y){
if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='x'){
return false;
}
return true;
}
class DSU{
int *parent;
int *rank;
int *tot;
public:
DSU(int n){
rank=new int[n+5];
parent=new int[n+5];
tot=new int [n+5];
for(int i=0;i<n+5;i++){
parent[i]=i;
rank[i]=0;
tot[i]=1;
}
}
int find(int i){
if(parent[i]==i){
return i;
}
return parent[i]=find(parent[i]);
}
void unite(int u,int v){
int i=find(u);
int j=find(v);
if(i!=j){
if(rank[i]>rank[j]){
parent[j]=i;
tot[i]+=tot[j];
}
else if(rank[i]<rank[j]){
parent[i]=j;
tot[j]+=tot[i];
}
else{
parent[j]=i;
rank[i]++;
tot[i]+=tot[j];
}
}
}
int total(int u){
return tot[u];
}
};
void precal(int n){
factorial[0]=1;
inv_fact[0]=1;
for (int i = 1; i <n; ++i)
{
factorial[i] = factorial[i - 1] * i % mod;
inv_fact[i] = inv_fact[i - 1] * power(i, mod - 2) % mod;
}
}
int choose(int n,int k){
if(k<0 || k>n) return 0;
return factorial[n] * inv_fact[n-k] % mod * inv_fact[k] %mod;
}
void Sieve(){
notprime[0]=notprime[1]=true;
for(int i=2;i<LIM+5;++i){
if(notprime[i]==false){
for(int j=i*i;j<LIM+5;j+=i){
notprime[j]=true;
}
}
}
}
void testcase(){
}
pii dfs(int i,int j,int k){
while(true){
if(grid[i][j]=='C'){
k=(k+1)%4;
}
else if(grid[i][j]=='A'){
k=(k+3)%4;
}
int x=i+dx[k];
int y=j+dy[k];
if(check(x,y)==false) return {i,j};
i=x,j=y;
}
}
void bfs(int l,int r){
cout<<"bfs "<<l<<" "<<r<<endl;
memset(vis,false,sizeof (vis));
for(int i=0;i<LIM*LIM+5;++i){
dist[i].clear();
}
int mn=inf;
int mx=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(dp[l][r][i][j]!=-1){
dist[dp[l][r][i][j]].push_back({i,j});
mn=min(mn,dp[l][r][i][j]);
mx=max(mx,dp[l][r][i][j]);
}
}
}
for(int i=0;i<=LIM+5;++i){
for(auto tmp:dist[i]){
int x=tmp.f;
int y=tmp.s;
if(vis[x][y]) continue;
vis[x][y]=1;
for(auto nxt:memodfs[x][y]){
int nx=nxt.f;
int ny=nxt.s;
if((dp[l][r][nx][ny]>dp[l][r][x][y]+1) || dp[l][r][nx][ny]==-1){
dp[l][r][nx][ny]=dp[l][r][x][y]+1;
dist[dp[l][r][nx][ny]].push_back({nx,ny});
}
}
}
}
}
void solve(){
//Sieve();
// precal();
#ifdef interactive
testcase();
#endif
cin>>num>>m>>n;
memset(dp,-1,sizeof dp);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>grid[i][j];
if('0'<=grid[i][j] && grid[i][j]<='9'){
x=grid[i][j]-'0';
dp[x][x][i][j]=0;
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=0;k<4;++k){
memodfs[i][j].push_back(dfs(i,j,k));
}
}
}
for(int d=0;d<num;++d){
for(int l=1;l+d<=num;++l){
int r=l+d;
for(int mid=l;mid<r;++mid){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if((dp[l][r][i][j]==-1 || dp[l][r][i][j]>dp[l][mid][i][j]+dp[mid+1][r][i][j])
&& (dp[l][mid][i][j]!=-1 && dp[mid+1][r][i][j]!=-1)){
dp[l][r][i][j]=dp[l][mid][i][j] + dp[mid+1][r][i][j];
}
}
}
}
bfs(l,r);
}
}
int ans=inf;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(dp[1][num][i][j]!=-1) ans = min(ans,dp[1][num][i][j]);
}
}
if(ans==inf) cout<<-1<<endl;
else cout<<ans<<endl;
}
signed main(){
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
test=1;
#ifdef multipletest
cin>>test;
#endif
while(test--){
solve();
#ifdef DEBUG
cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
