题目链接: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;
}
标签:Onsite,yi,xi,tot,int,Nanjing,p2,ACM,mx From: https://blog.51cto.com/u_12468613/6384495