2802：小游戏

这题可以使用递归来进行求解，让点分别向4个方向进行探索，直到遇到目标点，或者最后执行失败。如果找到了目标顶点，就对totalStep进行对比赋值。但step已经比目前的totalStep大时，应忽略这种情况，因为这样下去是没有意义的。

题目如下：

2802:小游戏

总时间限制:

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.

#include <bits/stdc++.h>
using namespace std;
int w,h;
char s[100][100];
bool mark[100][100];
int direction[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int totalStep=100000;
void findTotalPath(int x1,int y1,int x2,int y2,int direct,int step){
    //cout<<x1<<" "<<y1<<","<<x2<<" "<<y2<<endl;
    if(step>totalStep)
        return;
    if(x1==x2&&y1==y2){
        if(step<totalStep){
            totalStep=step;
        }
        return;
    }
    for(int i=0;i<4;i++){
        /*if((direct==0&&i==2)||(direct==1&&i==3)||(direct==2&&i==0)||(direct==3&&i==1))
            continue;*/
        int yy1=y1+direction[i][0];
        int xx1=x1+direction[i][1];
        //if((xx1<0)||(yy1<0)||(xx1>=h+2)||(yy1>=w+2)||(mark[yy1][xx1]==true)||((s[yy1][xx1]=='X')&&(yy1!=y2||xx1!=x2))) continue;
        /*cout<<x1<<" -"<<y1<<endl;
        cout<<xx1<<" "<<yy1<<endl;*/
        if((xx1>-1)&&(xx1<w+2)&&(yy1>-1)&&(yy1<h+2)&&(((s[yy1][xx1]==' ')&&(mark[yy1][xx1]==false))||((xx1==x2)&&(yy1==y2)&&(s[yy1][xx1]=='X')))){
        //if ((xx1 > -1) && (xx1< w + 2) && (yy1> -1) && (yy1 < h + 2)&& (((s[y][x] == ' ') && (mark[y][x] == false))||((xx1==x2)&& (yy1==y2) && (s[y][x] == ‘X’)))){
            mark[yy1][xx1]=true;
            if(direct!=i){
                findTotalPath(xx1,yy1,x2,y2,i,step+1);
            }else{
                findTotalPath(xx1,yy1,x2,y2,i,step);
            }
            mark[yy1][xx1]=false;
        }
    }
}
int main(){
    int id=1;
    while(1){
        /*cin>>w>>h;
        cin.ignore();*/
        scanf("%d %d",&w,&h);
        if(w==0&&h==0) break;
        /*for(int i=0;i<h+2;i++){
            s[i][0]=s[i][w+1]=' ';
        }
        for(int j=0;j<w+2;j++){
            s[0][j]=s[w+1][j]=' ';
        }*/
        for (int i = 0; i <100; i ++) s[0][i] =s[i][0] = ' ';
        for(int i=1;i<h+1;i++){
            getchar();
            //string str="";
            //getline(cin,str);
            for(int j=1;j<w+1;j++){
                //s[i][j]=str[j-1];
                s[i][j]=getchar();
            }
        }
        for (int i = 0; i <= w; i ++)
            s[h + 1][i + 1] = ' ';
        for (int i = 0; i <= h; i ++)
            s[i + 1][w + 1] = ' ';
        cout<<"Board #"<<id<<":"<<endl;
        id++;
        int x1,y1,x2,y2;
        int subId=0;
        while(1){
            subId++;
             totalStep=100000;
             memset(mark, false, sizeof(mark));
            cin>>x1>>y1>>x2>>y2;
            if(x1==0&&y1==0&&x2==0&&y2==0) break;
            int step=0;
            int direct=-1;
            findTotalPath(x1,y1,x2,y2,direct,step);
            if(totalStep<100000)
                cout<<"Pair "<<subId<<": "<<totalStep<<" segments."<<endl;
            else{
                cout<<"Pair "<<subId<<": "<<"impossible."<<endl;
            }
        }
        cout<<endl;
    }
}