题目源自 程序设计实习 12章 递归问题。
//思路根本方式是递归，走迷宫类问题，处在每一步上都要枚举下一步的方向，用MOVE数组来保存行进方向。
另外用mark数组来储存是否访问过
开始用puzzle数组来表示板子分布，然后在外面多加一圈来辅助计算。递归函数关键在于每一次调用时，先判断
当前步数是否大于最小步数，否则return，这样可以简化很多计算，同时，有一个递归出口，判断是否为结果，并
更新最小步数。
否则朝四个方向走，用枚举列出来，然后判断下一步是否符合条件。
条件1 nextX,nextY都处在board内部。
条件2 下一步没有访问过，并且是空格（可以连通）。
条件3 下一步是目的地。
此外这个题目是问的折现的个数，不是步数，所以还要有个方向变量来储存是否变向了，在代码中用if(direction == i)
来判断，如果相等，step就不用增加。
最后还要将mark标记为未访问
问题描述
• 当下面的情况满足时,
认为两个游戏卡片之间有一条路径相连:
• 路径只包含水平或者竖直的直线段
• 路径不能穿过别的游戏卡片
• 但是允许路径临时的离开矩形板
(1,3) (2,3) (5,3)
(3,4) (4,4) 输入 (1/2)
• 输入包括多组数据: 一个矩形板对应一组数据
• 第一行包括两个整数 w和h (1 <= w, h <= 75),
分别表示矩形板的宽度和长度
• 下面的h行, 每行包括w个字符, 表示矩形板上的游戏卡
片分布情况:
• 使用 ‘X’ 表示这个地方有一个游戏卡片
• 使用 空格 表示这个地方没有游戏卡片
5 输入 (2/2)
• 之后每行上包括4个整数:
x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h)
• 给出两个卡片在矩形板上的位置
注意: 矩形板左上角的坐标是(1,1)
输入保证这两个游戏卡片所处的位置是不相同的
如果一行上有4个0, 表示这组测试数据的结束
• 如果一行上给出w = h = 0, 那么表示所有的输入结束了
6 输出
• 对每一个矩形板, 输出一行 “Board #n:”, n是输入数据的
编号
• 对每一组需要测试的游戏卡片输出一行. 这一行的开头
是 “Pair m: ”, 这里m是测试卡片的编号（对每个矩形板,
编号都从1开始）
• 如果可以相连, 找到连接这两个卡片的所有路径中包括
线段数最少的路径, 输出 “k segments.”
k是找到的最优路径中包括的线段的数目
• 如果不能相连, 输出 “impossible.”
• 每组数据之后输出一个空行 7 样例输入
5 4
X X X X X
X X
X X X X
X X X
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0
#include<iostream>
using namespace std;
const int MAXN = 75;
char puzzle[MAXN+2][MAXN+2];
int mark[MAXN+2][MAXN+2];
int MOVE[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int w,h,minStep;
void search(int nowX,int nowY,int endX,int endY,int step,int direction);
int main(){
int boardNum(0);
while(cin>>w>>h)
{
if(w == 0&&h == 0)
return 0;
boardNum++;
cout<<"Board #"<<boardNum<<endl;
int i,j;
for(i = 0;i < MAXN;i++)
{
puzzle[0][i] = puzzle[i][0] = ' ';
}
for(i = 1;i <= w;i++)
{
getchar();
for(j = 1;j <= h;j++)
puzzle[i][j] = getchar();
}
for(i = 0;i <= w;i++)
puzzle[i+1][h+1] = ' ';
for(j = 0;j <=h;j++)
puzzle[w+1][j+1]=' ';
int beginX,beginY,endX,endY,countNum(0);
while(cin>>beginX>>beginY>>endX>>endY&&(beginX != 0)){
minStep = 1000;
countNum++;
memset(mark,0,sizeof(mark));
search(beginX,beginY,endX,endY,0,-1);
if(minStep == 1000)
cout<<"impossible"<<endl;
else
cout<<"Pair "<<countNum<<": "<<minStep<<" segments."<<endl;
}
cout<<endl;
}
return 0;
}
void search(int nowX,int nowY,int endX,int endY,int step,int direction){
if(step>=minStep)
return;
if((nowX == endX)&&(nowY == endY))
minStep=min(step,minStep);
for(int i = 0;i < 4;i++)
{
int nextX = MOVE[i][0]+nowX;
int nextY = MOVE[i][1]+nowY;
if(((nextX < w)&&(nextX > -1)&&(nextY < h)&&(nextY > -1))
&&(((nextX == endX)&&(nextY == endY)&&(puzzle[nextX][nextY] == 'X'))||((mark[nextX][nextY] == 0)&&puzzle[nextX][nextY] == ' ')))
{
mark[nextX][nextY] = 1;
if(direction == i)
search(nextX,nextY,endX,endY,step,i);
else
search(nextX,nextY,endX,endY,step+1,i);
mark[nextX][nextY] = 0;
}
}
}