【NOIP13 D2T3】华容道

Source and Judge

NOIP2013 提高组 D2T3
Luogu1979
Caioj1562

Problem

【Description】
给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。
游戏规则:

1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;
2. 有些棋子是固定的,有些棋子则是可以移动的;
3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EX 行第 EY 列,指定的可移动棋子的初始位置为第 SX 行第 SY 列,目标位置为第 TX 行第 TY 列。

假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。
【Input】
第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q;
接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。
接下来的 q 行,每行包含 6 个整数依次是Ex、Ey、SX、SY、TX、TY,每两个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。
【Output】
输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间.
如果某次游戏无法完成目标则输出−1。
【Limited conditions】
对于 30%的数据,1 ≤ n, m ≤ 10,q = 1;
对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10;
对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。
【Sample input】
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
【Sample output】
3
【Sample explanation】
棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋子。
第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示),游戏的目标是将初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。
移动过程如下:

第二次游戏,空白格子的初始位置是(1, 2)(图中空白所示),游戏的目标是将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,必然是从位置(2, 2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置, 游戏无法完成。

Record

5h

Analysis

请先思考后再展开

这是一道有脑子的搜索题

本质上就是空白的棋子到处和别人交换来达成目标,固定即不可交换
那么只要记录当前空白的位置和目标棋子的位置,就可以bfs了,据说有70分
时间复杂度:O(q(nm)^2),虽然稳tle,但考场上还是灰常值得的,也可以拿来拍

那我们梳理一下,可以这样想象:目标棋子和前面的空白交换,然后空白到后面之后,
又屁颠屁颠地跑到目标棋子前面……周边的普通棋子就像群众,一旦墙壁明确,存在性等同于空气。
怎么样,题意是不是明确了很多
显然仅当【空白在棋子旁边】的状态是有用的,仅有3600种!
但是我们虽然减少了状态,但并不代表忽略
bfs还是要有的,但不能每一次都搞呀,不然还是炸(特别是无解的时候)
因为如果指定棋子要移动,首先空格要到它旁边,而这段信息基本是公共的,尽管空格位置每次不同。也就是说,需要计算出dis(ax,ay,bx,by,d),分别表示空格和指定棋子位置以及最后空格在棋子的方位(0表示下方,1表示上方,2表示左方,3表示右方)
注意!没有必要枚举两点,用到的时候再处理
而且,不能忽略终点来bfs(我一开始是这样想的),因为bfs的要求是不能穿越终点(否则空格就会影响到当前棋子的值,而这个我们应单独处理)

那么搜索中有个强大的东西:A*!
教程的话,因为也在很多领域有应用,所以网上有灰常多的资料。
然后据说这东西的神奇之处在于,对于搜索题,帮你搞定很多想不到的剪枝。
但我对这东西不是太熟练,特别是其使用条件(适用范围)

  1. 首先,预处理出相邻可移动棋子的距离(用于求解中)
  2. 估价函数h(n):指定棋子到终点位置的曼哈顿距离
  3. 实际代价函数g(n):当前步数
  4. open表:搞一个小根堆即可( f*(n)=h*(n)+g*(n) )
  5. hash表:hash(state.x,state.y,state.d)=min{ g(state) }

那么,对于每一次求解,先预处理这一次bfs距离值
然后每一次取出小根堆中第一个来拓展
然后两种情况:

  1. 空格与棋子交换,注意方向调换
  2. 空格走到棋子其他侧

最后说一句,这道题既考验脑力,也考验码力,挺不错的

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=31;
const int tx[4]={1,-1,0,0};
const int ty[4]={0,0,1,-1};
//*******************全局定义*******************
int n,m;
int mp[MAXN][MAXN];
int dis[MAXN][MAXN][MAXN][MAXN][4];//不能碰到终点
//*******************预处理*******************
struct Pt
{
int x,y;
Pt(int tx=0,int ty=0) {x=tx;y=ty;}
};
queue<Pt> q1;
int tmp[MAXN][MAXN];
void bfs(Pt st,Pt ed)
{
memset(tmp,-1,sizeof(tmp));
for(int i=0;i<4;i++) dis[st.x][st.y][ed.x][ed.y][i]=-1;
q1.push(st);tmp[st.x][st.y]=0;
while(!q1.empty())
{
Pt now=q1.front();q1.pop();
for(int i=0;i<4;i++)
{
if(ed.x+tx[i]==now.x and ed.y+ty[i]==now.y) dis[st.x][st.y][ed.x][ed.y][i]=tmp[now.x][now.y];
int nx=now.x+tx[i],ny=now.y+ty[i];
if(nx<1 or nx>n or ny<1 or ny>m or !mp[nx][ny]) continue;
if(tmp[nx][ny]!=-1 or (nx==ed.x and ny==ed.y)) continue;//debug
tmp[nx][ny]=tmp[now.x][now.y]+1;
q1.push( Pt(nx,ny) );
}
}
}
//*******************实现*******************
struct Data
{
Pt now;//目标棋子
int d;//空白所在方向
int g,h;//实际步数、预估剩余步数
};
bool operator < (Data a,Data b) {return a.g+a.h>b.g+b.h;}
priority_queue<Data> q2;//小根堆
int hs[MAXN][MAXN][4];//Hash表,存储g()
void ins(Data x)
{
if(hs[x.now.x][x.now.y][x.d]>x.g)
{
hs[x.now.x][x.now.y][x.d]=x.g;
q2.push(x);
}
}
Pt e,st,ed;
int H(Pt now) {return myabs(now.x-ed.x)+myabs(now.y-ed.y);}
int solve()
{
scanf("%d%d%d%d%d%d",&e.x,&e.y,&st.x,&st.y,&ed.x,&ed.y);
if(st.x==ed.x and st.y==ed.y) return 0;//debug
memset(hs,127,sizeof(hs));
while(!q2.empty()) q2.pop();//debug
bfs(e,st);
for(int i=0;i<4;i++)
if(dis[e.x][e.y][st.x][st.y][i]!=-1)
ins( (Data){st,i,dis[e.x][e.y][st.x][st.y][i],H(st)} );
while(!q2.empty())
{
Data x=q2.top();q2.pop();
if(x.now.x==ed.x and x.now.y==ed.y) return x.g;
Pt kg=Pt(x.now.x+tx[x.d],x.now.y+ty[x.d]);//空格位置
//1. 空格与棋子交换,注意方向调换
ins( (Data){kg,x.d^1,x.g+1,H(kg)} );
//2. 空格走到棋子其他侧
for(int i=0;i<4;i++)
if(dis[kg.x][kg.y][x.now.x][x.now.y][i]!=-1)
ins( (Data){x.now,i,x.g+dis[kg.x][kg.y][x.now.x][x.now.y][i],x.h} );
}
return -1;
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
int q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&mp[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if(mp[i][j])
for(int t=0;t<4;t++) if(mp[i+tx[t]][j+ty[t]])
bfs( Pt(i,j),Pt(i+tx[t],j+ty[t]) );
while(q--) printf("%d\n",solve());
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/23c4.html
转载请注明出处,谢谢!