小游戲

題目描述

?? 一天早上，你起床的時候想：“我編程序這么牛，為什么不能靠這個掙點銀子呢？”因此你決定編寫一個小游戲。
?? 游戲在一個分割成w * h個長方格子的矩形板上進行。如圖所示，每個長方格子上可以有一張游戲卡片，也可以沒有。當下面的情況滿足時，我們認為兩個游戲卡片之間有一條路徑相連：
?? 路徑只包含水平或者豎直的直線段。路徑不能穿過別的游戲卡片。但是允許路徑臨時離開矩形板。
?? 下面是一個例子：

這里在(1, 3)和(4, 4)處的游戲卡片是可以相連的。而在 (2, 3) 和 (3, 4) 處的游戲卡是不相連的，因為連接他們的每條路徑都必須要穿過別的游戲卡片。
?? 你現(xiàn)在要在小游戲里面判斷是否存在一條滿足題意的路徑能連接給定的兩個游戲卡片。

關于輸入

?? 輸入包括多組數(shù)據(jù)。一個矩形板對應一組數(shù)據(jù)。每組數(shù)據(jù)的第一行包括兩個整數(shù)w和h (1 <= w, h <= 75)，分別表示矩形板的寬度和高度。下面的h行，每行包括w個字符，表示矩形板上的游戲卡片分布情況。使用‘X’表示這個地方有一個游戲卡片；使用空格表示這個地方?jīng)]有游戲卡片。之后的若干行，每行包括4個整數(shù)x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)，表示兩個卡片在矩形板上的位置（注意：矩形板左上角的坐標是(1, 1)）。如果一行上有4個0，則表示這組測試數(shù)據(jù)的結(jié)束。測試數(shù)據(jù)保證這兩個游戲卡片所處的位置是不相同的。
?? 如果一行上有2個0，那么表示所有的輸入結(jié)束了。

關于輸出

?? 對每一個矩形板，輸出一行“Board #n:”，這里n是輸入數(shù)據(jù)的編號（從1開始）。然后對于每一對需要測試的游戲卡片輸出一行。這一行的開頭是“Pair m: ”，這里m是測試卡片的編號（對每個矩形板，編號都從1開始）。接下來，如果可以相連，則找到連接這兩個卡片的所有路徑中包括線段數(shù)最少的路徑，輸出“k segments.”，這里k即是找到的最優(yōu)路徑中包括的線段的數(shù)目；如果不能相連，則輸出“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數(shù)組），這個地圖上標記了所有的游戲卡片的位置。探險家還有一個記事本（visited數(shù)組），用來記錄他已經(jīng)走過的位置，以防止他在迷宮中迷路。探險家還有一個指南針（dx和dy數(shù)組），告訴他可以向哪些方向移動。

當探險家開始他的探險時，他首先會檢查他是否已經(jīng)找到了寶藏（也就是目標游戲卡片）。如果找到了，他就會記錄下這條路徑的長度，并且和他之前找到的最短路徑進行比較，如果這條路徑更短，他就會記下這條路徑。如果沒有找到寶藏，他就會沿著四個方向繼續(xù)探險。在每個方向上，他都會檢查這個方向是否可以走（也就是這個位置沒有游戲卡片并且沒有被訪問過）。如果可以走，他就會標記這個位置已經(jīng)被訪問過，然后繼續(xù)探險。如果這個方向和他之前的方向不同，那么他就會把路徑長度加1，因為他需要轉(zhuǎn)彎。當他探險結(jié)束后，他會把這個位置的訪問標記清除，因為他可能會從其他路徑再次訪問這個位置。

這個程序的關鍵是深度優(yōu)先搜索算法。這個算法的思想就是"深入"探索每一個可能的路徑，直到找到目標或者無路可走。在這個過程中，程序使用了訪問標記數(shù)組來避免重復訪問，使用了路徑長度來剪枝，以提高搜索效率。

在主函數(shù)中，程序處理了多組測試數(shù)據(jù)。對于每一組數(shù)據(jù)，程序都會讀入矩形板的大小和游戲卡片的分布情況，然后對于每一對需要測試的游戲卡片，程序都會進行深度優(yōu)先搜索。搜索結(jié)束后，程序會輸出最短路徑長度或者"impossible"。

總的來說，這個程序就像一個探險家在迷宮中尋找寶藏，他會盡可能的尋找最短的路徑，如果找不到路徑，他就會告訴我們"impossible"。

代碼實現(xiàn)

（純享版）

#include <stdio.h>
#include <string.h>
#define min(x,y) x>y?y:xint 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]=' ';}elsescanf("%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);elseprintf("Pair %d: impossible.\n",countPair);}}return 0;
}

（詳細注釋版）

#include <stdio.h>
#include <string.h>  // 引入標準輸入輸出和字符串處理函數(shù)庫#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;// 定義深度優(yōu)先搜索函數(shù)
void dfs(int x,int y,int len,int pos){// 如果當前路徑長度大于等于最短路徑長度，結(jié)束搜索if(len>=minpath){return;}// 如果當前位置是目標位置，更新最短路徑長度，然后結(jié)束搜索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];// 檢查新的位置是否在矩形板內(nèi)，是否沒有游戲卡片，以及是否沒有被訪問過if(nx>=0 && nx<=w+1 && ny>=0 && ny<=h+1 &&((board[nx][ny]==' ' && visited[nx][ny]==0)||(nx==x2 && ny==y2))){// 標記新的位置已經(jīng)被訪問過visited[nx][ny]=1;// 如果新的方向和當前的方向相同，路徑長度不變，否則路徑長度加1if(pos==i){dfs(nx,ny,len,i);}else{dfs(nx,ny,len+1,i);}// 搜索結(jié)束后，清除新的位置的訪問標記visited[nx][ny]=0;}}
}int main(void) { // 讀入矩形板的高度和寬度while(scanf("%d%d",&h,&w)){getchar();// 如果高度和寬度都是0，結(jié)束循環(huán)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]=' ';}elsescanf("%c",&board[i][j]);}if(i>=1 && i<=w){getchar();}}// 初始化游戲卡片的計數(shù)器，增加矩形板的計數(shù)器，然后輸出矩形板的編號int countPair=0;countBoard++;printf("Board #%d:\n",countBoard);// 讀入需要測試的游戲卡片的位置while(scanf("%d%d%d%d",&y1,&x1,&y2,&x2)){countPair++;// 如果游戲卡片的位置都是0，結(jié)束循環(huán)if(x1==0 && y1==0 && x2==0 && y2==0){break;}// 初始化最短路徑長度，清除所有的訪問標記，然后開始深度優(yōu)先搜索minpath=1e9; memset(visited,0,sizeof(visited));dfs(x1,y1,0,-1);// 如果找到了路徑，輸出路徑長度，否則輸出"impossible"if(minpath!=1e9)printf("Pair %d: %d segments.\n",countPair,minpath);elseprintf("Pair %d: impossible.\n",countPair);}}return 0;  // 程序結(jié)束
}