Submission #115638

#	Time	Username	Problem	Language	Result	Execution time	Memory
115638		ckodser	Robots (APIO13_robots)	C++14	0 / 100	114 ms	132728 KiB

robots

#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[getid(i,j)].pb(c);
	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;
	return 0;
	while(1){
		bool typ;
		cin>>typ;
		if(typ==1){
		ll i,j,l,r;
		cin>>i>>j>>l>>r;
		cout<<dp[getid(i,j)][l][r]<<endl;
		}else{
			ll i,j;
			cin>>i>>j;
			for(auto e:inp[getid(i,j)]){
				pri(e);
			}
			cout<<endl;
		}
	}

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40