首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【POJ】1101 - The Game(bfs,连连看问题)

【POJ】1101 - The Game(bfs,连连看问题)

作者头像
FishWang
发布2025-08-26 19:44:50
发布2025-08-26 19:44:50
8100
代码可运行
举报
运行总次数:0
代码可运行

The Game

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 9808

Accepted: 2989

Description

One morning, you wake up and think: "I am such a good programmer. Why not make some money?'' So you decide to write a computer game. The game takes place on a rectangular board consisting of w * h squares. Each square might or might not contain a game piece, as shown in the picture. One important aspect of the game is whether two game pieces can be connected by a path which satisfies the two following properties: It consists of straight segments, each one being either horizontal or vertical. It does not cross any other game pieces. (It is allowed that the path leaves the board temporarily.) Here is an example:

The game pieces at (1,3) and at (4, 4) can be connected. The game pieces at (2, 3) and (3, 4) cannot be connected; each path would cross at least one other game piece. The part of the game you have to write now is the one testing whether two game pieces can be connected according to the rules above.

Input

The input contains descriptions of several different game situations. The first line of each description contains two integers w and h (1 <= w,h <= 75), the width and the height of the board. The next h lines describe the contents of the board; each of these lines contains exactly w characters: a "X" if there is a game piece at this location, and a space if there is no game piece. Each description is followed by several lines containing four integers x1, y1, x2, y2 each satisfying 1 <= x1,x2 <= w, 1 <= y1,y2 <= h. These are the coordinates of two game pieces. (The upper left corner has the coordinates (1, 1).) These two game pieces will always be different. The list of pairs of game pieces for a board will be terminated by a line containing "0 0 0 0". The entire input is terminated by a test case starting with w=h=0. This test case should not be procesed.

Output

For each board, output the line "Board #n:", where n is the number of the board. Then, output one line for each pair of game pieces associated with the board description. Each of these lines has to start with "Pair m: ", where m is the number of the pair (starting the count with 1 for each board). Follow this by "ksegments.", where k is the minimum number of segments for a path connecting the two game pieces, or "impossible.", if it is not possible to connect the two game pieces as described above. Output a blank line after each board.

Sample Input

代码语言:javascript
代码运行次数:0
运行
复制
5 4
XXXXX
X   X
XXX X
 XXX 
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0

Sample Output

代码语言:javascript
代码运行次数:0
运行
复制
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.

Source

Mid-Central European Regional Contest 1999

检查了一个半小时的bug,一直WA掉,网上的测试数据一组组全部通过,就是代码过不去。

最后师父检查出来了,原来是map数组没有清零,留下当个教训吧。

以前做题都是用%s输入地图,就这一次用%c,以前不用初始化,但是用%c得初始化,因为前一次如果地图大的话,保存过的痕迹会影响下一次计算,因为这道题要在地图之外的一圈进行操作。

代码如下:

代码语言:javascript
代码运行次数:0
运行
复制
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
char map[88][88];
int vis[88][88];
int mx[4]={0,0,1,-1};
int my[4]={1,-1,0,0};
int stx,sty,endx,endy;
int ti;		//需要的线段数
int w,h;		//w为宽(x轴),h为高(y轴)
struct node
{
	int x,y,time;		//time为转弯次数
}a,b,c;
int check(int x,int y)
{
	if (x<0 || x>w+1 || y<0 || y>h+1)
		return 1;		//返回1时则不能通过(此处不考虑撞墙的情况) 
	return 0; 
}
int bfs()
{
	queue<node>q;
	a.x=stx;
	a.y=sty;
	a.time=0;
	vis[stx][sty]=1;
	q.push(a);
	while (!q.empty())
	{
		a = q.front();
		ti = a.time+1;
		q.pop();
		for (int i=0;i<4;i++)
		{
			b.x = a.x+mx[i];
			b.y = a.y+my[i];
			if (check (b.x,b.y))
				continue;
			while (1)		//若该点合法,则按照此方向走下去 
			{
				if (b.x == endx && b.y == endy)
					return ti;
				if (check (b.x,b.y) || map[b.x][b.y] == 'X')
					break;		//一直走直到结束或撞墙 
				if (!vis[b.x][b.y])		//如果此点已经扫描过,则跳过继续此方向扫描
				{
					c.x = b.x;
					c.y = b.y;
					c.time = ti;
					q.push(c);
					vis[c.x][c.y] = 1;		//千万记得标记 
				}
				b.x += mx[i];
				b.y += my[i];
			}
		}
	}
	return -1;
}
int main()
{
	int u = 1;
	int ans;
	while (~scanf ("%d %d",&w,&h) && (w||h)) 
	{
		memset (map,'0',sizeof(map));
		getchar();		//吸收换行符
		int num = 1;
		printf ("Board #%d:\n",u++);
		for (int i=1;i<=h;i++)
		{
			for (int j=1;j<=w;j++)
				scanf ("%c",&map[j][i]);
			getchar();
		}
		while (~scanf ("%d %d %d %d",&stx,&sty,&endx,&endy))
		{
			if (!stx && !sty && !endx && !endy)
				break;
			memset (vis,0,sizeof(vis));
			ans = bfs();
			printf("Pair %d: ",num++);
            if(ans == -1)    
				puts("impossible.");
            else    
				printf("%d segments.\n",ans);
		}
		printf ("\n");
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-08-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档