问题描述

2017-10-03 19-08-13 创建的截图.png

2017-10-03 19-08-26 创建的截图.png

2017-10-03 19-08-32 创建的截图.png

2017-10-03 19-08-36 创建的截图.png

2017-10-03 19-08-56 创建的截图.png

2017-10-03 19-09-00 创建的截图.png

2017-10-03 19-09-10 创建的截图.png

问题分析

2017-10-03 19-13-59 创建的截图.png

2017-10-03 19-14-12 创建的截图.png

2017-10-03 19-14-15 创建的截图.png

2017-10-03 19-14-18 创建的截图.png

2017-10-03 19-14-28 创建的截图.png

2017-10-03 19-14-30 创建的截图.png

2017-10-03 19-14-33 创建的截图.png

程序实现

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN=75;

char board[MAXN+2][MAXN+2];//定义矩形板
int mark[MAXN+2][MAXN+2];//定义标记数组
int direc[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};//定义方向

int w,h,minSteps;

void searchPath(int curX,int curY,int tarX,int tarY,int steps,int preDirec)
    {
//X方向上下,Y方向左右
    if(steps>minSteps) return;//当前路径数大于minSteps,返回------优化策略
    if((curX==tarX)&&(curY==tarY)) {//到达终点
            if(minSteps>steps) minSteps=steps;//更新最小路径数
            return;
            }
    for(int i=0; i<4; i++) {//枚举下一步的方向
            int X=curX+direc[i][0];//得到新的位置
            int Y=curY+direc[i][1];
            if((X>-1&&X<h+2&&Y>-1&&Y<w+2)&&((mark[X][Y]==0&&board[X][Y]==' ')||((X==tarX)&&(Y==tarY)&&board[X][Y]=='X'))) {
                    mark[X][Y]=1;
                    //上一步方向和当前方向相同,则递归搜索时steps不变,否则steps+1
                    if(i==preDirec) searchPath(X,Y,tarX,tarY,steps,i);
                    else searchPath(X,Y,tarX,tarY,steps+1,i);
                    mark[X][Y]=0;//回溯,该位置未曾走过
                    }
            }
    }

int main()
    {
    int countsB=0;
    while(cin>>w>>h) {
        if(w==0&&h==0) break;
        countsB++;
        cout<<"Board #"<<countsB<<":"<<endl;
        memset(board,' ',sizeof(board));
        for(int i=1; i<h+1; i++){
            getchar();//读入换行符
        for(int j=1; j<w+1; j++)
            board[i][j]=getchar();
            }
        int countsXY=0;
        int x1,y1,x2,y2;
        while(cin>>y1>>x1>>y2>>x2) {
            if(x1==0&&y1==0&&x2==0&&y2==0) break;
            memset(mark,0,sizeof(mark));
            minSteps=10000000;//初始化minSteps为一个很大的值
            countsXY++;
            searchPath(x1,y1,x2,y2,0,-1);
            if(minSteps==10000000)
                cout<<"Pair "<<countsXY<<":"<<" impossible."<<endl;
            else
                cout<<"Pair "<<countsXY<<": "<<minSteps<<" segments."<<endl;
            }
        cout<<endl;
        }
    return 0;
}