TopCoder SRM 360 Div1 Medium PrinceOfPersia

問題

hxwのグリッドで表される迷路がある。
迷路の中に二人がいる。

maze[i][j]が'#'であるマスは壁で、進入することができない。
maze[i][j]が'.'であるマスは何もないマスで、進入することができる。
maze[i][j]が'P'のマス（迷路上に二つ）は、二人のスタートの位置を表す。

二人は、上下左右に隣接するマスへ移動することを繰り返して、同じマスへ到達する。
二人が同じマスへ到達できないように、迷路上にいくつかブロックを置く。

最低でいくつのブロックをおく必要があるか、求めよ。

制約条件

h≦10
w≦10

方針

フロー。
各マスにINおよびOUTの頂点を作り、
INからOUTへ容量1の辺を張る。
各マスのOUTから、隣接するマスのINへ容量1の辺を張る。

一方のPのマスのOUTを湧き出し、もう一方のPのマスのINを吸い込みとして、最大流を流せば、最大流＝最小カットの関係から、流量が置くべきブロックの数となる。

ソースコード

最大流は蟻本実装。

const int MAX_V=202;
struct edge{ int to,cap,rev; };
vector<edge> G[MAX_V];

int level[MAX_V],iter[MAX_V];

void add_edge(int from,int to,int cap){
	G[from].pb((edge){ to, cap, G[to].size() });
	G[to].pb((edge){ from, 0, G[from].size()-1 });
}

void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> q;
	level[s]=0;
	q.push(s);
	while(!q.empty()){
		int v=q.front(); q.pop();
		rep(i,G[v].size()){
			edge &e=G[v][i];
			if(e.cap>0&&level[e.to]<0){
				level[e.to]=level[v]+1;
				q.push(e.to);
			}
		}
	}
}
int dfs(int v,int t,int f){
	if(v==t)return f;
	for(int &i=iter[v];i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.cap>0&&level[v]<level[e.to]){
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		bfs(s);
		if(level[t]<0)return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f=dfs(s,t,inf))>0)flow+=f;
	}
}
const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};

class PrinceOfPersia {
	public:
	int minObstacles(vector <string> maze) 
	{
		int h=maze.size(), w=maze[0].size();
		int V=h*w*2+2, cnt=0;
		
		rep(i,V)G[i].clear();
		rep(i,h)rep(j,w)add_edge(i*w+j<<1,i*w+j<<1|1,1);
		
		rep(i,h)rep(j,w)if(maze[i][j]!='#'){
			if(maze[i][j]=='P'){
				if(++cnt==1)add_edge(V-2,i*w+j<<1|1,inf);
				else add_edge(i*w+j<<1,V-1,inf);
			}
			rep(d,4){
				int y=i+dy[d], x=j+dx[d];
				if(y<0||x<0||y>=h||x>=w)continue;
				if(maze[i][j]=='P'&&maze[y][x]=='P')return -1;
				if(maze[y][x]!='#')add_edge(i*w+j<<1|1,y*w+x<<1,1);
			}
		}
		return max_flow(V-2,V-1);
	}
};

最初、接続関係をもつDPだと思って頑張って書いたがTLE...

int h,w;
map<pair<ll,int>,int> dp[11];

inline void merge(vi &v,int a,int b){
	int t=v[b];
	rep(i,v.size())if(v[i]==t)v[i]=v[a];
}
inline void reorder(vi &v){
	int to[11]={},k=0;
	rep(i,v.size())if(v[i]&&!to[v[i]])to[v[i]]=++k;
	rep(i,v.size())if(v[i])v[i]=to[v[i]];
}
inline ll packv(vi &a){
	ll base=1, res=0;
	rep(i,a.size())res+=a[i]*base, base*=11;
	return res;
}
inline int packp(vi &p){
	int base=1, res=0;
	rep(i,p.size()){
		res+=base*(p[i]+1);
		base=50;
	}
	return res;
}

class PrinceOfPersia {
	public:
	int minObstacles(vector <string> maze) 
	{
		h=maze.size(); w=maze[0].size();
		rep(i,11)dp[i].clear();
		
		vi v,p;
		rep(i,w)v.pb(i+1);
		dp[0][mp(packv(v),packp(p))]=0;
		rep(i,h)fr(it,dp[i]){
			v.clear(); p.clear();
			for(ll j=0, t=it->first.first;j<w;j++, t/=11)v.pb(t%11);
			if(it->first.second/50)p.pb(it->first.second/50-1);
			if(it->first.second%50)p.pb(it->first.second%50-1);
			
			rep(mask,1<<w){
				int cur[11]={}, to[11]={}, ncost=it->second, np_;
				ll nv_;
				vi nv,np;
				
				rep(j,w){
					if(maze[i][j]!='.'&&(mask&1<<j))goto NEXT;
					if(maze[i][j]=='#'||(mask&1<<j))cur[j]=1;
				}
				rep(j,w)nv.pb(cur[j]?0:j+1);
				//merge
				rep(j,w)rep(k,j)if(!cur[j]&&!cur[k]&&v[j]&&v[j]==v[k])merge(nv,j,k);
				rep(j,w-1)if(!cur[j]&&!cur[j+1])merge(nv,j,j+1);
				
				reorder(nv);
				rep(j,w){
					if(nv[j])to[v[j]]=nv[j];
					if(mask&1<<j)ncost++;
				}
				to[0]=0;
				rep(j,p.size())np.pb(to[p[j]]);
				rep(j,w)if(maze[i][j]=='P')np.pb(nv[j]);
				
				if(np.size()>1&&np[0]&&np[0]==np[1])continue;
				
				//rep(j,w)cerr<<nv[j]<<(j==w-1?"\n":" ");
				nv_=packv(nv); np_=packp(np);
				
				if(!dp[i+1].count(mp(nv_,np_))||dp[i+1][mp(nv_,np_)]>ncost)
				dp[i+1][mp(nv_,np_)]=ncost;
				
				NEXT:;
			}
		}
		
		int ans=inf;
		fr(it,dp[h]){
			p.clear();
			if(it->first.second/50)p.pb(it->first.second/50-1);
			if(it->first.second%50)p.pb(it->first.second%50-1);
			//rep(i,p.size())cerr<<p[i]<<(i==p.size()-1?"\n":" ");
			//dbg(it->second);
			if(p[0]==0||p[0]!=p[1])ans=min(ans,it->second);
		}
		return ans==inf?-1:ans;
	}
};