免费网站自助制作,节约化网站群建设情况,舆情优化,网站建设备案费用小游戏
题目描述 一天早上#xff0c;你起床的时候想#xff1a;“我编程序这么牛#xff0c;为什么不能靠这个挣点银子呢#xff1f;”因此你决定编写一个小游戏。 游戏在一个分割成w * h个长方格子的矩形板上进行。如图所示#xff0c;每个长方格子上可以有一张游戏…小游戏
题目描述 一天早上你起床的时候想“我编程序这么牛为什么不能靠这个挣点银子呢”因此你决定编写一个小游戏。 游戏在一个分割成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则表示这组测试数据的结束。测试数据保证这两个游戏卡片所处的位置是不相同的。 如果一行上有2个0那么表示所有的输入结束了。
关于输出 对每一个矩形板输出一行“Board #n:”这里n是输入数据的编号从1开始。然后对于每一对需要测试的游戏卡片输出一行。这一行的开头是“Pair m: ”这里m是测试卡片的编号对每个矩形板编号都从1开始。接下来如果可以相连则找到连接这两个卡片的所有路径中包括线段数最少的路径输出“k segments.”这里k即是找到的最优路径中包括的线段的数目如果不能相连则输出“impossible.”。 注意每个矩形板之后须输出一个空行。
例子输入
5 4
XXXXX
X X
XXX XXXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
4 4
XXXX
XXXX
XXXX
XXXX
1 1 2 1
2 2 3 2
1 1 3 1
3 4 4 3
2 1 2 4
1 1 2 2
0 0 0 0
0 0例子输出
Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.
Board #2:
Pair 1: 1 segments.
Pair 2: 1 segments.
Pair 3: 3 segments.
Pair 4: 4 segments.
Pair 5: 5 segments.
Pair 6: impossible.
解题分析
我们可以设计一个探险家找宝藏的程序利用dfs和剪枝的策略去寻找最短路径然而其实本题使用bfs会比较好不过我们暂时用dfs来做。
首先你可以把这个程序想象成一个探险家在一个迷宫中寻找宝藏。这个迷宫就是我们的矩形板而探险家的任务就是找到两个游戏卡片之间的最短路径。
探险家有一个地图board数组这个地图上标记了所有的游戏卡片的位置。探险家还有一个记事本visited数组用来记录他已经走过的位置以防止他在迷宫中迷路。探险家还有一个指南针dx和dy数组告诉他可以向哪些方向移动。
当探险家开始他的探险时他首先会检查他是否已经找到了宝藏也就是目标游戏卡片。如果找到了他就会记录下这条路径的长度并且和他之前找到的最短路径进行比较如果这条路径更短他就会记下这条路径。如果没有找到宝藏他就会沿着四个方向继续探险。在每个方向上他都会检查这个方向是否可以走也就是这个位置没有游戏卡片并且没有被访问过。如果可以走他就会标记这个位置已经被访问过然后继续探险。如果这个方向和他之前的方向不同那么他就会把路径长度加1因为他需要转弯。当他探险结束后他会把这个位置的访问标记清除因为他可能会从其他路径再次访问这个位置。
这个程序的关键是深度优先搜索算法。这个算法的思想就是深入探索每一个可能的路径直到找到目标或者无路可走。在这个过程中程序使用了访问标记数组来避免重复访问使用了路径长度来剪枝以提高搜索效率。
在主函数中程序处理了多组测试数据。对于每一组数据程序都会读入矩形板的大小和游戏卡片的分布情况然后对于每一对需要测试的游戏卡片程序都会进行深度优先搜索。搜索结束后程序会输出最短路径长度或者impossible。
总的来说这个程序就像一个探险家在迷宫中寻找宝藏他会尽可能的寻找最短的路径如果找不到路径他就会告诉我们impossible。
代码实现
纯享版
#include stdio.h
#include string.h
#define min(x,y) xy?y:xint w,h,x1,y1,x2,y2;
char board[80][80];
int visited[80][80]{0};
int minpath1e9;
const int dx[]{-1,0,1,0};
const int dy[]{0,-1,0,1};
int countBoard0;void dfs(int x,int y,int len,int pos){if(lenminpath){return;}if(xx2 yy2){minpathmin(minpath,len);return;}for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx0 nxw1 ny0 nyh1 ((board[nx][ny] visited[nx][ny]0)||(nxx2 nyy2))){visited[nx][ny]1;if(posi){dfs(nx,ny,len,i);}else{dfs(nx,ny,len1,i);}visited[nx][ny]0;}}
}int main(void) { while(scanf(%d%d,h,w)){getchar();if(h0 w0) break;for(int i0;iw1;i){for(int j0;jh1;j){if(i0 || j0 || iw1 || jh1){board[i][j] ;}elsescanf(%c,board[i][j]);}if(i1 iw){getchar();}}int countPair0;countBoard;printf(Board #%d:\n,countBoard);while(scanf(%d%d%d%d,y1,x1,y2,x2)){countPair;if(x10 y10 x20 y20){break;}minpath1e9; memset(visited,0,sizeof(visited));dfs(x1,y1,0,-1);if(minpath!1e9)printf(Pair %d: %d segments.\n,countPair,minpath);elseprintf(Pair %d: impossible.\n,countPair);}}return 0;
}详细注释版
#include stdio.h
#include string.h // 引入标准输入输出和字符串处理函数库#define min(x,y) xy?y:x // 定义求最小值的宏// 定义全局变量
int w,h,x1,y1,x2,y2;
char board[80][80];
int visited[80][80]{0};
int minpath1e9;
const int dx[]{-1,0,1,0};
const int dy[]{0,-1,0,1};
int countBoard0;// 定义深度优先搜索函数
void dfs(int x,int y,int len,int pos){// 如果当前路径长度大于等于最短路径长度结束搜索if(lenminpath){return;}// 如果当前位置是目标位置更新最短路径长度然后结束搜索if(xx2 yy2){minpathmin(minpath,len);return;}// 在四个方向上进行搜索for(int i0;i4;i){// 计算新的位置int nxxdx[i],nyydy[i];// 检查新的位置是否在矩形板内是否没有游戏卡片以及是否没有被访问过if(nx0 nxw1 ny0 nyh1 ((board[nx][ny] visited[nx][ny]0)||(nxx2 nyy2))){// 标记新的位置已经被访问过visited[nx][ny]1;// 如果新的方向和当前的方向相同路径长度不变否则路径长度加1if(posi){dfs(nx,ny,len,i);}else{dfs(nx,ny,len1,i);}// 搜索结束后清除新的位置的访问标记visited[nx][ny]0;}}
}int main(void) { // 读入矩形板的高度和宽度while(scanf(%d%d,h,w)){getchar();// 如果高度和宽度都是0结束循环if(h0 w0) break;// 读入矩形板上的游戏卡片分布情况for(int i0;iw1;i){for(int j0;jh1;j){// 如果位置在矩形板的边界上设置为没有游戏卡片否则读入游戏卡片的分布情况if(i0 || j0 || iw1 || jh1){board[i][j] ;}elsescanf(%c,board[i][j]);}if(i1 iw){getchar();}}// 初始化游戏卡片的计数器增加矩形板的计数器然后输出矩形板的编号int countPair0;countBoard;printf(Board #%d:\n,countBoard);// 读入需要测试的游戏卡片的位置while(scanf(%d%d%d%d,y1,x1,y2,x2)){countPair;// 如果游戏卡片的位置都是0结束循环if(x10 y10 x20 y20){break;}// 初始化最短路径长度清除所有的访问标记然后开始深度优先搜索minpath1e9; memset(visited,0,sizeof(visited));dfs(x1,y1,0,-1);// 如果找到了路径输出路径长度否则输出impossibleif(minpath!1e9)printf(Pair %d: %d segments.\n,countPair,minpath);elseprintf(Pair %d: impossible.\n,countPair);}}return 0; // 程序结束
}
