[递归回溯]连接卡片最短路径

小游戏

题目描述

?? 一天早上，你起床的时候想：“我编程序这么牛，为什么不能靠这个挣点银子呢？”因此你决定编写一个小游戏。
?? 游戏在一个分割成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 X
 XXX
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) x>y?y:x

int w,h,x1,y1,x2,y2;
char board[80][80];
int visited[80][80]={0};
int minpath=1e9;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int countBoard=0;

void dfs(int x,int y,int len,int pos){
    if(len>=minpath){
        return;
    }
    if(x==x2 && y==y2){
        minpath=min(minpath,len);
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0 && nx<=w+1 && ny>=0 && ny<=h+1 &&((board[nx][ny]==' ' && visited[nx][ny]==0)||(nx==x2 && ny==y2))){
            visited[nx][ny]=1;
            if(pos==i){
                dfs(nx,ny,len,i);
            }
            else{
                dfs(nx,ny,len+1,i);
            }
            visited[nx][ny]=0;
        }
    }
}

int main(void) { 
	while(scanf("%d%d",&h,&w)){
	    getchar();
	    if(h==0 && w==0) break;
	    for(int i=0;i<=w+1;i++){
	        for(int j=0;j<=h+1;j++){
	            if(i==0 || j==0 || i==w+1 || j==h+1){
	                board[i][j]=' ';
	            }
	            else
	            scanf("%c",&board[i][j]);
	        }
	        if(i>=1 && i<=w){
	            getchar();
	        }
	    }
	    int countPair=0;
	    countBoard++;
	    printf("Board #%d:\n",countBoard);
	    while(scanf("%d%d%d%d",&y1,&x1,&y2,&x2)){
	        countPair++;
	        if(x1==0 && y1==0 && x2==0 && y2==0){
	            break;
	        }
	        minpath=1e9; memset(visited,0,sizeof(visited));
	        dfs(x1,y1,0,-1);
	        if(minpath!=1e9)
	        printf("Pair %d: %d segments.\n",countPair,minpath);
	        else
	        printf("Pair %d: impossible.\n",countPair);
	    }
	}
	return 0;
}

（详细注释版）

#include <stdio.h>
#include <string.h>  // 引入标准输入输出和字符串处理函数库

#define min(x,y) x>y?y:x  // 定义求最小值的宏

// 定义全局变量
int w,h,x1,y1,x2,y2;
char board[80][80];
int visited[80][80]={0};
int minpath=1e9;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int countBoard=0;

// 定义深度优先搜索函数
void dfs(int x,int y,int len,int pos){
    // 如果当前路径长度大于等于最短路径长度，结束搜索
    if(len>=minpath){
        return;
    }
    // 如果当前位置是目标位置，更新最短路径长度，然后结束搜索
    if(x==x2 && y==y2){
        minpath=min(minpath,len);
        return;
    }
    // 在四个方向上进行搜索
    for(int i=0;i<4;i++){
        // 计算新的位置
        int nx=x+dx[i],ny=y+dy[i];
        // 检查新的位置是否在矩形板内，是否没有游戏卡片，以及是否没有被访问过
        if(nx>=0 && nx<=w+1 && ny>=0 && ny<=h+1 &&((board[nx][ny]==' ' && visited[nx][ny]==0)||(nx==x2 && ny==y2))){
            // 标记新的位置已经被访问过
            visited[nx][ny]=1;
            // 如果新的方向和当前的方向相同，路径长度不变，否则路径长度加1
            if(pos==i){
                dfs(nx,ny,len,i);
            }
            else{
                dfs(nx,ny,len+1,i);
            }
            // 搜索结束后，清除新的位置的访问标记
            visited[nx][ny]=0;
        }
    }
}

int main(void) { 
    // 读入矩形板的高度和宽度
    while(scanf("%d%d",&h,&w)){
        getchar();
        // 如果高度和宽度都是0，结束循环
        if(h==0 && w==0) break;
        // 读入矩形板上的游戏卡片分布情况
        for(int i=0;i<=w+1;i++){
            for(int j=0;j<=h+1;j++){
                // 如果位置在矩形板的边界上，设置为没有游戏卡片，否则读入游戏卡片的分布情况
                if(i==0 || j==0 || i==w+1 || j==h+1){
                    board[i][j]=' ';
                }
                else
                scanf("%c",&board[i][j]);
            }
            if(i>=1 && i<=w){
                getchar();
            }
        }
        // 初始化游戏卡片的计数器，增加矩形板的计数器，然后输出矩形板的编号
        int countPair=0;
        countBoard++;
        printf("Board #%d:\n",countBoard);
        // 读入需要测试的游戏卡片的位置
        while(scanf("%d%d%d%d",&y1,&x1,&y2,&x2)){
            countPair++;
            // 如果游戏卡片的位置都是0，结束循环
            if(x1==0 && y1==0 && x2==0 && y2==0){
                break;
            }
            // 初始化最短路径长度，清除所有的访问标记，然后开始深度优先搜索
            minpath=1e9; memset(visited,0,sizeof(visited));
            dfs(x1,y1,0,-1);
            // 如果找到了路径，输出路径长度，否则输出"impossible"
            if(minpath!=1e9)
            printf("Pair %d: %d segments.\n",countPair,minpath);
            else
            printf("Pair %d: impossible.\n",countPair);
        }
    }
    return 0;  // 程序结束
}