ACM-ICPC Nanjing Onsite 2018 - K(随机枚举+四维bfs)

题目链接:https://nanti.jisuanke.com/t/33680

解题思路:

随机两个袋鼠的位置，使得让他们相遇，那么这个操作就是一个四维的bfs，前两维代表第一只袋鼠的位置，后两维表示第二只袋鼠的位置。这样随机枚举最多是N*M次。

所以时间复杂度最最最最坏情况也就O(N^3*M^3)。

#include <bits/stdc++.h>
using namespace std;
const int mx = 22;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
int n,m,xi[mx*mx],yi[mx*mx];
char str[mx][mx];
int tot,cnt[mx][mx];
int vis[mx][mx][mx][mx];
int q[mx*mx],head,ans[mx*mx*mx*mx],top;
int p[mx][mx][mx][mx]; 
struct node
{
	int x1,y1;
	int x2,y2;
}path[mx][mx][mx][mx];
char dire(int x)
{
	if(x==0) return 'R';
	if(x==1) return 'L';
	if(x==2) return 'U';
	return 'D';
}
void go(int &fx,int &fy,int x,int y,int d)
{
	fx = x + dx[d];
	fy = y + dy[d];
}
bool check(int x,int y)
{
	if(cnt[x][y]==-1) return 0;
	if(x<0||x==n) return 0;
	if(y<0||y==m) return 0;
	return 1;
}
node merge(int p1,int p2,int time)
{
	vis[xi[p1]][yi[p1]][xi[p2]][yi[p2]] = time;
	queue <node> que;
	que.push(node{xi[p1],yi[p1],xi[p2],yi[p2]});
	p[xi[p1]][yi[p1]][xi[p2]][yi[p2]] = -1;
	int fx,fy,px,py;
	while(!que.empty()){
		node now = que.front();
		que.pop();
		for(int i=0;i<4;i++){
			go(fx,fy,now.x1,now.y1,i);
			go(px,py,now.x2,now.y2,i);
			if(!check(fx,fy)) fx = now.x1,fy = now.y1;
			if(!check(px,py)) px = now.x2,py = now.y2;
			if(vis[fx][fy][px][py]!=time)
			{
				path[fx][fy][px][py] = now;
				p[fx][fy][px][py] = i;
				if(fx==px&&fy==py) return node{fx,fy,fx,fy};
				que.push(node{fx,fy,px,py});
				vis[fx][fy][px][py] = time;
			}
		}
	}
}
void up(char d)
{
	int col,row;
	if(d=='U') col = 0,row = 1;
	else col = 1,row = 0;
	for(int i=row;i<n;i++){
		for(int j=col;j<m;j++){
			if(cnt[i][j]==-1) continue;
			if(d=='U'){
				if(cnt[i-1][j]!=-1)
				cnt[i-1][j] += cnt[i][j],cnt[i][j] = 0;
			}else{
				if(cnt[i][j-1]!=-1)
				cnt[i][j-1] += cnt[i][j],cnt[i][j] = 0;
			}
		}
	}
}
void down(char d)
{
	int col,row;
	if(d=='D') col = m-1,row = n-2;
	else col = m-2,row = n-1;
	for(int i=row;~i;i--){
		for(int j=col;~j;j--){
			if(cnt[i][j]==-1) continue;
			if(d=='D'){
				if(cnt[i+1][j]!=-1)
				cnt[i+1][j] += cnt[i][j],cnt[i][j] = 0;
			}else{
				if(cnt[i][j+1]!=-1)
				cnt[i][j+1] += cnt[i][j],cnt[i][j] = 0;
			}
		}
	}
}
void Get()
{
	for(int i=0;i<head;i++){
		char d = dire(q[i]);
		if(d=='D'||d=='R') down(d);
		else up(d);
	}
}
void find(int x1,int y1,int x2,int y2)
{
	int i = p[x1][y1][x2][y2];
	if(i==-1) return ;
	node now = path[x1][y1][x2][y2];
	find(now.x1,now.y1,now.x2,now.y2);;
	ans[top++] = i, q[head++] = i;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",str[i]);
		for(int j=0;j<m;j++){
			cnt[i][j] = str[i][j] - '0';
			if(cnt[i][j]) xi[tot] = i,yi[tot++] = j;
			else cnt[i][j] = -1;
		}
	}
	int cas = 1;
	while(tot>1){
		int p1 = tot-1,p2 = (tot-1)/2;
		node eng = merge(p1,p2,cas++);
		tot = head = 0;
		find(eng.x1,eng.y1,eng.x2,eng.y2);
		Get();
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(cnt[i][j]>0) xi[tot] = i,yi[tot++] = j;
			}
		}
	}
	for(int i=0;i<top;i++) putchar(dire(ans[i]));
	puts("");
	return 0;
}