ZOJ1361解题报告 acm解题报告

HoledoxMoving

Time Limit:10SecondsMemoryLimit:32768 KB

During winter, the most hungry and severe time, Holedox sleeps inits lair. When spring comes, Holedox wakes up, moves to the exit ofits lair, comes out, and begins its new life.

Holedox is a special snake, but its body is not very long. Itslair is like a maze and can be imagined as a rectangle with n*msquares. Each square is either a stone or a vacant place, and onlyvacant places allow Holedox to move in. Using ordered pair of rowand column number of the lair, the square of exit located at(1,1).

Holedox's body, whose length is L, can be represented block byblock. And let B1(r1,c1) B2(r2,c2) .. BL(rL,cL) denote its L lengthbody, where Bi is adjacent to Bi+1 in the lair for 1 i L-1, and B1is its head, BL is its tail.

To move in the lair, Holedox chooses an adjacent vacant squareof its head, which is neither a stone nor occupied by its body.Then it moves the head into the vacant square, and at the sametime, each other block of its body is moved into the squareoccupied by the corresponding previous block.

For example, in the Figure 2, at the beginning the body ofHoledox 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 squarethat the head can be moved into, Holedox moves its head intoB1'(5,1), then moves B2 into B1, B3 into B2, and B4 into B3. Thusafter one step, the body of Holedox locates inB1(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 eachblock of Holedox's body, your task is to write a program to tellthe minimal number of steps that Holedox has to take to move itshead to reach the square of exit (1,1).

Input

The input consists of several test cases. The first line of eachcase 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 columnsin the lair and the body length of Holedox, respectively. The nextL lines contain a pair of row and column number each, indicatingthe original position of each block of Holedox's body, fromB1(r1,c1) to BL(rL,cL) orderly, where 1 ri n, and 1 ci m,1 i L. Thenext line contains an integer K, representing the number of squaresof stones in the lair. The following K lines contain a pair of rowand column number each, indicating the location of each square ofstone. 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 numberfollowed 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
ZOJ1361解题报告 acm解题报告
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) toreach the square of exit with minimal number of step, which isnine.

蛇的爬动(HoledoxMoving)

题目描述:

在冬天,天气最恶劣的时期,蛇待在洞穴里冬眠。当春天来临的时候,蛇苏醒了,爬到洞穴的出口,然后爬出来,开始它的新生活。

蛇的洞穴象一个迷宫,我们可以把它想象成一个由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 64

41

42

32

31

3

23

33

34

4 44

23

13

14

24

4

21

22

34

42

0 00

样例输出:

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。

因此,可以用一个数组记录已经扩展的状态:

charstate[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<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

usingnamespace std;

#defineMAXMN 20

structpoint//表示方格的位置

{

int x, y;

};

structsnake//问题的状态:表示蛇每段位置的结构体

{

int step;//已走的步数

point pos[8];//L段蛇头和蛇身所占据的位置

int direction[8];//direction[1]~direction[L-1]为每一段相对于前一段的方向

};

queue<snake> Q;//队列中的结点为蛇在每时刻的位置

int n, m,L, K;//洞穴的大小,蛇的长度, 石头的数目

intmap[MAXMN+2][MAXMN+2];//地图:0-空的方格, 1-蛇, 2-石头

intdir[4][2] = { {-1,0}, {0,1}, {1,0}, {0,-1} }; //4个相邻方向:上(0)、右(1)、下(2)、左(3)

charstate[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<L; 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 ) returnhd.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<L; j++ ) //判断(x,y)位置是否被蛇身占用了

{

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<L; 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<L; 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<K; i++ )

{

scanf( "%d%d", &x, &y );

map[x][y] = 2;

}

printf( "Case %d: %dn", kase++, BFS( start ) );

while( !Q.empty( ) ) Q.pop( );

}

return 0;

}


  

爱华网本文地址 » http://www.413yy.cn/a/25101012/116629.html

更多阅读

ZOJ1361解题报告 acm解题报告

HoledoxMovingTime Limit:10SecondsMemoryLimit:32768 KBDuring winter, the most hungry and severe time, Holedox sleeps inits lair. When spring comes, Holedox wakes up, moves to the exit ofits lair, comes out, and

《核电站问题》解题报告 红沿河核电站实习报告

核电站问题TimeLimit:1000MS MemoryLimit:65536KDescription   一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。  任务:对于给定的N和M,求不发生爆炸的放

课题研究报告范文-工作报告 课题研究中期报告范文

第1篇课题研究报告范文-----小学数学课题研究报告本学期,有四个课题要结题,分别是朱春燕《小学数学开放性问题设计的研究》,肖烈《小学高段学生“日记竞赛”的实践研究》,齐丽琴《小学生语文阅读习惯培养的研究》,陆立军《农村小学生课外

加强和完善我州街道社区人大工作的调研报告 人大调研报告

加强和完善我州街道社区人大工作的调研报告刘昌刚4月3日至4日,我带领州人大联工委调研组一行3人,轻车简从深入泸溪县就街道人大工委和社区代表作用发挥专题开展全州新型城镇化调研,调研组在泸溪县人大机关召开了由部分省州县人大代表

农民工工伤案件研究报告 农民工研究报告

来源:北京市农民工法律援助工作站 作者:不详 发布时间:2008-5-13 12:37:00 浏览次数:1461次此信息由 小张001 志愿者发布[提要] 农民工工伤案件研究报告2004年1月1日开始实施的《工伤保险条例》将农民工全部纳入了工伤保险的范畴,而工

声明:《ZOJ1361解题报告 acm解题报告》为网友好好活着分享!如侵犯到您的合法权益请联系我们删除