【广搜】OJ2.5 小游戏

1804:小游戏

查看提交统计提问 总时间限制:  1000ms  内存限制:  65536kB 描述 一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个赚点小钱呢？”因此你决定编写一个小游戏。 游戏在一个分割成w * h个正方格子的矩形板上进行。如图所示，每个正方格子上可以有一张游戏卡片，当然也可以没有。 当下面的情况满足时，我们认为两个游戏卡片之间有一条路径相连： 路径只包含水平或者竖直的直线段。路径不能穿过别的游戏卡片。但是允许路径临时的离开矩形板。下面是一个例子：  这里在 (1, 3)和 (4, 4)处的游戏卡片是可以相连的。而在 (2, 3) 和 (3, 4) 处的游戏卡是不相连的，因为连接他们的每条路径都必须要穿过别的游戏卡片。 你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片。 输入 输入包括多组数据。一个矩形板对应一组数据。每组数据包括的第一行包括两个整数w和h (1 <= w, h <= 75)，分别表示矩形板的宽度和长度。下面的h行，每行包括w个字符，表示矩形板上的游戏卡片分布情况。使用‘X’表示这个地方有一个游戏卡片；使用空格表示这个地方没有游戏卡片。 之后的若干行上每行上包括4个整数x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)。给出两个卡片在矩形板上的位置（注意：矩形板左上角的坐标是(1, 1)）。输入保证这两个游戏卡片所处的位置是不相同的。如果一行上有4个0，表示这组测试数据的结束。 如果一行上给出w = h = 0，那么表示所有的输入结束了。 输出 对每一个矩形板，输出一行“Board #n:”，这里n是输入数据的编号。然后对每一组需要测试的游戏卡片输出一行。这一行的开头是“Pair m: ”，这里m是测试卡片的编号（对每个矩形板，编号都从1开始）。接下来，如果可以相连，找到连接这两个卡片的所有路径中包括线段数最少的路径，输出“k segments.”，这里k是找到的最优路径中包括的线段的数目；如果不能相连，输出“impossible.”。 每组数据之后输出一个空行。 样例输入 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 样例输出 Board #1: Pair 1: 4 segments. Pair 2: 3 segments. Pair 3: impossible. 来源 翻译自Mid-Central European Regional Contest 1999的试题 【分析】 最开始打算用深搜来做。为此付出了总共10多次的WA与TLE的代价。 如果用堵的方法来剪枝，那么很多更优的接将无法找到。但如果不剪，那么会超时，甚至会因递归层数太多而栈溢出。 所以说，个人认为最为方便、快捷、难度低的方法就是广搜。从起点出发，向四面八方遍历。 注意： 1、一定要保存棋盘的初始状态。 2、在输入新一个棋盘时，要重置保存棋盘的初始状态的数组。 3、两个棋盘的答案输出之间要隔一个空行，否则会PE。 【程序】 #include<cstdio> #include<cstring> #include<queue> #include<iostream> using namespace std; queue<int>x, y, sum, d; char m[80][80], p[80][80]; int r, c, set, times, ex, ey, ans = 1 << 30; int fy[4] = {-1, 1, 0, 0}, fx[4] = {0, 0, -1, 1}; void bfs() { do { int a = x.front(), b = y.front(), e = d.front(), i, s = sum.front(); x.pop(); y.pop(); sum.pop(); d.pop(); if(a== ex && b == ey) { ans = min(s, ans); continue; } m[b][a] = 'X'; for(i = 0; i < 4; i++) { if(a + fx[i] >= 0 && a + fx[i] <= c + 1 && b + fy[i] >= 0 && b + fy[i] <= r + 1 && m[b + fy[i]][a + fx[i]] != 'X') { x.push(a + fx[i]); y.push(b + fy[i]); sum.push(e == i ? s : s + 1); d.push(i); } } }while(!x.empty()); } int main() { //freopen("1.txt", "w", stdout); int i, sx, sy; while(~scanf("%d%d", &c, &r)) { if(!r) return 0; set++; printf("Board #%d:\n", set); for(i = 0; i <= r; i++) fgets(p[i] + 1, 100, stdin); while(~scanf("%d%d%d%d", &sx, &sy, &ex, &ey)) { if(!sx) break; times++; printf("Pair %d: ", times); memcpy(m, p, sizeof(p)); m[ey][ex] = m[sy][sx] = ' '; x.push(sx); y.push(sy); d.push(-1); sum.push(0); bfs(); if(ans == 1 << 30) printf("impossible.\n"); else printf("%d segments.\n", ans); ans = 1 << 30; while(!x.empty()) { x.pop(); y.pop(); d.pop(); sum.pop(); } } times = 0; memset(p, 0, sizeof(p)); printf("\n"); } }