解题报告ZOJ1361
解题报告ZOJ1361
Holedox Moving
Time Limit: 10 Seconds Memory Limit: 32768 KB
During winter, the most hungry and severe time, Holedox sleeps in its lair. When spring comes, Holedox wakes up, moves to the exit of its lair, comes out, and begins its new life.
Holedox is a special snake, but its body is not very long. Its lair is like a maze and can be imagined as a rectangle with n*m squares. Each square is either a stone or a vacant place, and only vacant places allow Holedox to move in. Using ordered pair of row and column number of the lair, the square of exit located at (1,1).
Holedox's body, whose length is L, can be represented block by block. And let B1(r1,c1) B2(r2,c2) .. BL(rL,cL) denote its L length body, where Bi is adjacent to Bi+1 in the lair for 1 i L-1, and B1 is its head, BL is its tail.
To move in the lair, Holedox chooses an adjacent vacant square of its head, which is neither a stone nor occupied by its body. Then it moves the head into the vacant square, and at the same time, each other block of its body is moved into the square occupied by the corresponding previous block.
For example, in the Figure 2, at the beginning the body of Holedox can be represented as B1(4,1) B2(4,2) B3(3,2)B4(3,1). During the next step, observing that B1'(5,1) is the only square that the head can be moved into, Holedox moves its head into B1'(5,1), then moves B2 into B1, B3 into B2, and B4 into B3. Thus after one step, the body of Holedox locates in B1(5,1)B2(4,1)B3(4,2) B4(3,2) (see the Figure 3).
Given the map of the lair and the original location of each block of Holedox's body, your task is to write a program to tell the minimal number of steps that Holedox has to take to move its head to reach the square of exit (1,1).
Input
The input consists of several test cases. The first line of each case contains three integers n, m (1 n, m 20) and L (2 L 8), representing the number of rows in the lair, the number of columns in the lair and the body length of Holedox, respectively. The next L lines contain a pair of row and column number each, indicating the original position of each block of Holedox's body, from B1(r1,c1) to BL(rL,cL) orderly, where 1 ri n, and 1 ci m,1 i L. The next line contains an integer K, representing the number of squares of stones in the lair. The following K lines contain a pair of row and column number each, indicating the location of each square of stone. Then a blank line follows to separate the cases.
The input is terminated by a line with three zeros.
Note: Bi is always adjacent to Bi+1 (1 i L-1) and exit square (1,1) will never be a stone.
Output
For each test case output one line containing the test case number followed by the minimal number of steps Holedox has to take. "-1" means no solution for that case.
Sample Input
5 6 4
4 1
4 2
3 2
3 1
3
2 3
3 3
3 4
4 4 4
2 3
1 3
1 4
2 4
4
2 1
2 2
3 4
4 2
0 0 0
Sample Output
Case 1: 9
Case 2: -1
Note: In the above sample case, the head of Holedox can follows (4,1)'(5,1)'(5,2)'(5,3)'(4,3)'(4,2)'(4,1)'(3,1)'(2,1)'(1,1) to reach the square of exit with minimal number of step, which is nine.
蛇的爬动(Holedox Moving)
题目描述：
在冬天，天气最恶劣的时期，蛇待在洞穴里冬眠。当春天来临的时候，蛇苏醒了，爬到洞穴的出口，然后爬出来，开始它的新生活。
蛇的洞穴象一个迷宫，我们可以把它想象成一个由n×m个正方形区域组成的长方形。每个正方形区域要么被石头占据了，要么是一块空地，蛇只能在空地间爬动。洞穴的行和列都是有编号的，且出口在(1,1)位置。
蛇的身躯，长为L，用一块连一块的形式来表示。假设用B1(r1,c1)，B2(r2,c2)，...，BL(rL,cL)表示它的L块身躯，其中，Bi与Bi+1相邻，i=1, ..., L-1；B1为蛇头，BL为蛇尾。
为了在洞穴中爬动，蛇选择与蛇头相邻的一个空的正方形区域，这个区域既没有被石头占据，也没有被它的身躯占据。当蛇头移动到这个空地，这时，它的身躯中其他每一块都移动它前一块身躯之前所占据的空地上。
例如，图2.20(a)所示的洞穴中，蛇的初始位置为：B1(4,1)，B2(4,2)，B3(3,2)和B4(3,1)。在下一步，蛇头只能移动到B1'(5,1)位置。蛇头移动到B1'(5,1)位置后，则B2移动到B1原先所在的位置，B3移动到B2原先所在的位置，B4移动到B3原先所在的位置。因此移动一步后，蛇的身躯位于B1(5,1)，B2(4,1)，B3(4,2)和B4(3,2)，如图2.20(b)所示。
给定洞穴的地图，以及蛇的每块身躯的初始位置，你的任务是编写程序，计算蛇头爬到出口(1,1)位置所需的最少步数。
输入描述：
输入文件包含多个测试数据。每个测试数据的第1行为3个整数：n，m和L，1≤n, m≤20，2≤L≤8，分别代表洞穴的行、列，以及蛇的长度。接下来有L行，每行有一对整数，分别表示行和列，代表蛇的每一块身躯的初始位置，依顺序分别为B1(r1,c1)～BL(rL,cL)。接下来一行包含一个整数K，表示洞穴中石头的数目。接下来的K行，每行包含一对整数，分别表示行和列，代表每一块石头的位置。每两个测试数据之间有一个空行。输入文件的最后一行为三个0，代表输入结束。
注意：Bi总是与Bi+1相邻，1≤i≤L-1，出口位置(1,1)从不会被石头占据。
输出描述：
对输入文件中的每个测试数据，输出一行：首先是测试数据的序号；然后是蛇爬到洞穴出口所需的最少步数，如果没有解，则输出-1。
样例输入：
5 6 4
4 2
3 2
3 1
3
2 3
3 3
3 4
4 4 4
2 3
1 3
1 4
2 4
4
2 1
2 2
3 4
4 2
0 0 0
样例输出：
Case 1: 9
Case 2: -1
注意：第一个测试数据中，蛇头按如下顺序移动，所需的步数是最少的：(4,1)，(5,1)，(5,2)，(5,3)，(4,3)，(4,2)，(4,1)，(3,1)，(2,1)，(1,1)，所需步数为9。
题目类型：BFS搜索
解题思路：
该题是图论里经典的图的遍历问题。要实现BFS遍历，最关键的问题在于如何判重。现在要解决的问题是状态的判重：采用BFS算法思想，从某个状态(结点)扩展出的状态结点中，要判断这些状态结点在此之前的搜索过程中是否出现过，如果出现过，则不扩展。
表示问题状态方法：
蛇头位置＋除蛇头外每一段相对于前一段的位置（上(0)、右(1)、下(2)、左(3)），这种表示方法所表示的状态数为20×20×47 = 6553600。
因此，可以用一个数组记录已经扩展的状态：
char state[6553600]; //char：1字节
state[i]为1表示状态i已经访问过
初始状态为：2,3,0,3,3，将这个状态表示转换成一个整数
四进制“0,3,3”转换成十进制为15（设为c）
转换方法：(((x-1)*m+y-1))*pow(4.0,L-1.0)+c
解决了状态判重后就可以模拟队列进行BFS搜索，得出最优解。
代码：
#include
#include
#include
#include
using namespace std;
#define MAXMN 20
struct point //表示方格的位置
{
int x, y;
};
struct snake //问题的状态：表示蛇每段位置的结构体
{
int step; //已走的步数
point pos[8]; //L段蛇头和蛇身所占据的位置
int direction[8]; //direction[1]～direction[L-1]为每一段相对于前一段的方向
};
queue
int n, m, L, K; //洞穴的大小，蛇的长度, 石头的数目
int map[MAXMN+2][MAXMN+2]; //地图：0－空的方格, 1－蛇, 2－石头
int dir[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} }; //4个相邻方向：上(0)、右(1)、下(2)、左(3) char state[6553600]; //用于状态判重,state[i]为1表示状态i已经访问过
int cal( snake s ) //计算状态s对应的整数值
{
int x = s.pos[0].x, y = s.pos[0].y;
int c = 0;
for( int i=1; i c = c*4 + s.direction[i]; return ((((x-1)*m+y-1))*pow(4.0,L-1.0)+c); } int BFS( snake s ) //从状态s开始进行BFS搜索 { int i, j, w; //循环变量 Q.push( s ); state[cal(s)] = 1; snake hd; //从队列头出队列的位置 while( !Q.empty( ) ) //当队列非空 { hd = Q.front( ); Q.pop( ); int x0 = hd.pos[0].x, y0 = hd.pos[0].y; if( x0==1 && y0==1 ) return hd.step; //判断蛇头是否位于(1,1) for( i=0; i<4; i++ ) { //判断能否移动到相邻位置(x,y) int x = x0 + dir[i][0], y = y0 + dir[i][1]; if( x>=1 && x<=n && y>=1 && y<=m && map[x][y]!=2 ) //排除边界和石头位置 { for( j=0; j { if( hd.pos[j].x==x && hd.pos[j].y==y ) break; } if( j>=L ) //(x,y)位置没有被蛇身占用 { snake t; t.pos[0].x = x; t.pos[0].y = y; //蛇头新位置 t.direction[1] = i>1 ? i-2 : i+2; for( w=1; w { t.pos[w].x = hd.pos[w-1].x; t.pos[w].y = hd.pos[w-1].y; if(w>1) t.direction[w] = hd.direction[w-1]; } t.step = hd.step + 1; int c = cal( t ); if( !state[c] ) //状态c没有访问过 { Q.push( t ); state[c] = 1; } } }//end of if }//end of for }//end of while return -1; } int main( ) { int i; //循环变量 int x, y; //石头位置 int kase = 1; //测试数据序号 // freopen( "input.in", "r", stdin ); while( 1 ) { scanf( "%d%d%d", &n, &m, &L ); if( n==0 && m==0 && L==0 ) break; memset( map, 0, sizeof(map) ); memset( state, 0, sizeof(state) ); snake start; //蛇的初始状态 for( i=0; i { scanf( "%d%d", &start.pos[i].x, &start.pos[i].y ); if( i>0 ) { int xa = start.pos[i].x - start.pos[i-1].x; int ya = start.pos[i].y - start.pos[i-1].y; if( xa==-1 && ya==0 ) start.direction[i] = 0; else if( xa==0 && ya==1 ) start.direction[i] = 1; else if( xa==1 && ya==0 ) start.direction[i] = 2; else if( xa==0 && ya==-1 ) start.direction[i] = 3; } } start.step = 0; scanf( "%d", &K ); //读入石头数目 for( i=0; i { scanf( "%d%d", &x, &y ); map[x][y] = 2; } printf( "Case %d: %d\n", kase++, BFS( start ) ); while( !Q.empty( ) ) Q.pop( ); } return 0; } 报告人：张海峰 2011-4-29