#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=510;
const ll inf=1e9+800;
const ll di[4]={-1,0 ,+1,0 };
const ll dj[4]={0 ,+1,0 ,-1};
ll w,h;
string s[maxn];
vector<pair<pii,ll> > out[maxn][maxn][4];
bool good[maxn][maxn][4];
vector<ll> inp[maxn*maxn];
ll dp[maxn*maxn][10][10];
ll getid(ll a,ll b){
return a*maxn+b;
}
void pri(ll a){
cout<<a/maxn<<' '<<a%maxn<<" &*& ";
}
ll chimishe(char s,ll d){
if(s=='C'){
d=(d+1)%4;
}if(s=='A'){
d=(d+3)%4;
}return d;
}
pair<pii,ll> movein(ll i,ll j,ll d){
i+=di[d];
j+=dj[d];
if(i<0 || i>=h || j<0 || j>=w || s[i][j]=='x'){
i-=di[d];
j-=dj[d];
}
return mp(mp(i,j),d);
}
void dfs(ll i,ll j,ll d,ll c){
if(getid(i,j)!=c)
inp[c].pb(getid(i,j));
for(auto e:out[i][j][d]){
dfs(e.F.F,e.F.S,e.S,c);
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
cin>>n>>w>>h;
for(ll i=0;i<h;i++){
cin>>s[i];
}
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
if('1'<=s[i][j] && s[i][j]<='9'){
s[i][j]-='1';
}
}
}
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
if(s[i][j]!='x'){
for(ll d=0;d<4;d++){
pair<pii,ll> e=movein(i,j,chimishe(s[i][j],d));
if(e.F.F==i && e.F.S==j){
good[i][j][d]=1;
}else{
out[e.F.F][e.F.S][e.S].pb(mp(mp(i,j),d));
}
}
}
}
}
for(ll i=0;i<maxn;i++){
for(ll j=0;j<maxn;j++){
for(ll d=0;d<4;d++){
if(good[i][j][d]){
dfs(i,j,d,getid(i,j));
}
}
}
}/*
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
cout<<i<<' '<<j<<'^';
for(auto e:inp[getid(i,j)]){
pri(e);
}
cout<<endl;
}
}*/
for(ll i=0;i<maxn*maxn;i++)for(ll l=0;l<9;l++)for(ll r=0;r<9;r++)dp[i][l][r]=inf;
for(ll t=1;t<=n;t++){
for(ll l=0;l+t-1<n;l++){
ll r=l+t-1;
set<pii> st;
for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){
ll u=getid(i,j);
ll res=inf;
if(t==1 && s[i][j]==l){
res=0;
}
for(ll z=l;z<r;z++){
res=min(res,dp[u][l][z]+dp[u][z+1][r]);
}
if(res!=inf){
// cout<<l<<' '<<r<<":"<<res<<"$";
// pri(u);
// cout<<endl;
st.insert(mp(res,u));
}
}
while(st.size()){
pii e=(*st.begin());
st.erase(e);
ll v=e.S;
ll w=e.F;
// pri(v);
// cout<<"%"<<w<<endl;
if(dp[v][l][r]>w){
// cout<<"MIAD\n";
dp[v][l][r]=w;
for(auto e:inp[v]){
st.insert(mp(w+1,e));
}
}
}/*
for(ll i=0;i<h;i++){
for(ll j=0;j<w;j++){
cout<<i<<' '<<j<<' '<<l<<' '<<r<<":"<<dp[getid(i,j)][l][r]<<endl;
}
} */
}
}
ll ans=inf;
for(ll i=0;i<maxn*maxn;i++){
ans=min(ans,dp[i][0][n-1]);
}
cout<<ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
111 ms |
132728 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
132728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
111 ms |
132728 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
132728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
111 ms |
132728 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
132728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
111 ms |
132728 KB |
Output is correct |
| 2 |
Incorrect |
112 ms |
132728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
