Description
小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:- 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;
- 有些棋子是固定的,有些棋子则是可以移动的;
- 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。
给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EX_i 行第 EY_i 列,指定的可移动棋子的初始位置为第 SX_i 行第 SY_i 列,目标位置为第 TX_i 行第 TY_i 列。
假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。Input Description
第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q;
接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。接下来的 q 行,每行包含 6 个整数依次是 EX_i、EY_i、SX_i、SY_i、TX_i、TY_i,每两个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。Output Description
输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完成目标则输出-1。
Sample Input
3 4 2
0 1 1 10 1 1 00 1 0 03 2 1 2 2 21 2 2 2 3 2Sample Output
2
-1Data Size & Hint
【样例说明】
棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋子。第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示),游戏的目标是将初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。移动过程如下:第二次游戏,空白格子的初始位置是(1, 2)(图中空白所示),游戏的目标是将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。
要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,必然是从位置(2,2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置,游戏无法完成。
【数据范围】
对于 30%的数据,1 ≤ n, m ≤ 10,q = 1;对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10;对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。Solution
(思路其实蛮清晰的,可能自己代码打得少,
一开始调了蛮久的,后来发现只是一些小细节。
比如进队操作多写了一个++tail,
memset(dis,0x3f,sizeof (deep));之类的 QAQ。)
下面是具体内容:
假设青蓝格为起点,
红格为终点,白格为空白格。若要从起点向某个方向走,前提是白格在该方向上,如该图所示。 起点向该方向走后, 此时白格对于起点, 在原来的反方向, 也就是说其实每一次的移动, 实质是白格在青蓝格上下左右四个方向的某个方向, 向青蓝格所要走的下一格移动, 当然,刚开始的时候白格可能不在四个方向上, 所以我们先做一遍bfs把白格到起点四个方向的最短路径计算出来; 那么接下来每一次走动都是 dis[i][j][h]=min{dis[i][j][k]+move[i][j][k][h]+1}; (也就是走到i,j的k方向上的最短路径+白格移动到h距离+青蓝格移动1格) 这里提到了move这个数组,其表示的是i,j某个方向到另一个方向的最短路径长,因为i<=j<=30,并且棋盘是不改变的,所以我们可以预处理出这个数组。 然后最后计算最短路可以写一个spfa。最后青蓝格移动到终点的四个方向,
白格移动到终点,然后青蓝格移动到白格,到达终点,如图。#include#include #include #define up 1#define down 2#define left 3#define right 4const int inf=0x3f3f3f;int n,m,q;int chess[35][35];int move[35][35][5][5];int deep[35][35],dis[35][35][5];bool done[35][35],in[35][35][5];int ex,ey,sx,sy,tx,ty;struct node{ int x,y,k;} t1,t2,q2[30005];struct queue1{ int x,y;} q1[30005];int other(int k){ if(k==up) return down; if(k==down) return up; if(k==left) return right; if (k==right) return left; return 0;}node go(node t,int k){ node n=t; if (k==up) n.x--; if (k==down) n.x++; if (k==left) n.y--; if (k==right) n.y++; return n;}int bfs(node x,node y){ if (!chess[x.x][x.y]||!chess[y.x][y.y]) return inf; memset(deep,0x3f,sizeof deep); memset(done,false,sizeof done); int head=0,tail=1; q1[1].x=x.x,q1[1].y=x.y; done[x.x][x.y]=true; deep[x.x][x.y]=0; while (head