이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*input
2 3 1
1x2
*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("unroll-loo8ps,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FIlim(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;
//const ld PI=acos(-1);
const ld eps=1e-9;
const int maxn=5e2+5;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define FILL(x,y) memset(x,y,sizeof(x))
inline ll mult(ll a,ll b){
a%=MOD,b%=MOD;
return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
if(b<=0) return 1;
a%=MOD;
ll res=1;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a);
b>>=1;
}
return res;
}
char arr[maxn][maxn];
int dp[maxn][maxn][10][10];
vector<pii> v[maxn*maxn];
pii to[maxn][maxn][4];
int n,m;
bool isin(int x,int y){
if(x<0 or x>=n or y<0 or y>=m) return false;
return true;
}
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0);
int rob;
cin>>rob>>n>>m;
swap(n,m);
REP(i,n) cin>>arr[i];
REP(i,n) REP(j,m) REP(a,rob) REP(b,rob) dp[i][j][a][b]=INF;
REP(i,n){
REP(j,m){
if(isdigit(arr[i][j])){
int z=arr[i][j]-'0'-1;
dp[i][j][z][z]=0;
}
}
}
REP(i,n){
REP(j,m){
if(arr[i][j]=='x') continue;
REP(k,4){
int dir=k;
if(arr[i][j]=='A') dir+=3;
if(arr[i][j]=='C') dir++;
dir%=4;
int x=i,y=j;
while(true){
int nx=x+dx[dir],ny=y+dy[dir];
if(!isin(nx,ny) or arr[nx][ny]=='x') break;
x=nx,y=ny;
if(arr[x][y]=='A') dir+=3;
if(arr[x][y]=='C') dir++;
dir%=4;
}
to[i][j][k]={x,y};
//cout<<i<<' '<<j<<' '<<k<<' '<<x<<' '<<y<<'\n';
}
}
}
// return 0;
REP(i,rob){
REP(l,rob-i){
int r=i+l;
REP(a,n){
REP(b,m){
if(arr[a][b]=='x') continue;
for(int k=l;k<r;k++){
MNTO(dp[a][b][l][r],dp[a][b][l][k]+dp[a][b][k+1][r]);
}
if(dp[a][b][l][r]!=INF) v[dp[a][b][l][r]].pb({a,b});
}
}
REP(a,n*m){
for(auto x:v[a]){
//cout<<x.f<<' '<<x.s<<'\n';
if(dp[x.f][x.s][l][r]!=a) continue;
REP(k,4){
pii z=to[x.f][x.s][k];
if(dp[z.f][z.s][l][r]>dp[x.f][x.s][l][r]+1){
dp[z.f][z.s][l][r]=dp[x.f][x.s][l][r]+1;
v[dp[z.f][z.s][l][r]].pb(z);
}
}
}
v[a].clear();
v[a].shrink_to_fit();
}
}
}
int ans=INF;
REP(i,n) REP(j,m) MNTO(ans,dp[i][j][0][rob-1]);
if(ans==INF) ans=-1;
cout<<ans;
}
# | 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... |