二、递归(一)

一、基本思想

二、 实例-小游戏

#include "stdafx.h"
#include<iostream>
#include<memory>
#define MAXIN 75  
using namespace std;


char board[MAXIN + 2][MAXIN + 2];  //定义矩阵板，外围为空
int minstep, w, h, to[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; //定义方向
bool mark[MAXIN + 2][MAXIN + 2]; //定义标记数组

//搜索函数
void Search(int now_x, int now_y, int end_x, int end_y, int step, int f) {
    if (step > minstep) {
        return;    //当前路径数大于minstep， 返回->优化策略
    }
    if (now_x == end_x && now_y == end_y) {   //到达终点
        if (minstep > step)  {   //更新最小路径数 
            minstep = step;
        }
        return;
    }
    for (int i = 0; i<4; i++) {  //枚举下一步的方向
        int x = now_x + to[i][0];
        int y = now_y + to[i][1];
        if ((x>-1) && (x<w + 2) && (y>-1) && (y<h + 2) && (((board[y][x] == ' ') && (mark[y][x] == false)) || ((x == end_x) && (y == end_y) && (board[y][x] == 'X')))) {
            mark[y][x] = true;  //如果新位置，有效标记该位置
            //上一步方向与当前方向相同，则递归搜索时step不变，否则step+1
            if (f == i) {
                Search(x, y, end_x, end_y, step, i);
            }
            else {
                Search(x, y, end_x, end_y, step + 1, i);
            }
            mark[y][x] = false;  //回溯，该位置未曾走过
        }
    }
}



int main(){
    int boardnum = 0;
    cout << "input w, h:";
    while (scanf_s("%d  %d", &w, &h)){
        if (w == 0 && h == 0)break;
        boardnum++;
        printf("Board#%d:\n", boardnum);
        printf("h:%d w: %d\n", w, h);
        int i, j;
        for (i = 0; i < MAXIN + 2; i++)board[0][i] = board[i][0] = ' ';
        cout << "print matrix:\n";
        for (i = 1; i <=h; i++){//读入矩形板的布局
            getchar();  //读取缓存区中回车键
            for (j = 1; j<=w; j++)board[i][j] = getchar();
        }
        for (i = 0; i <= h+1; i++){
            for (j = 0; j <= w+1; j++){
                cout << board[i][j];
            }
            cout << "\n";
        }

        //在下方和右侧添加空白
        for (i = 0; i <= w; i++)
            board[h + 1][i+1] = ' ';
        for (i = 0; i <= h; i++)
            board[i + 1][w + 1] = ' ';
        int begin_x, begin_y, end_x, end_y, count = 0;
        cout << "input begin_x begin_y  end_x end_y:\n";
        while (cin>>begin_x>>begin_y>>end_x>>end_y ){
            //读入起始点和终点
            if (begin_x == 0)break;
            printf("%d %d %d %d \n", begin_x,begin_y, end_x, end_y);
            cout << "begin search...\n";
            count++;
            minstep = 1000;
            memset(mark, false, sizeof(mark));
            //递归搜索
            Search(begin_x, begin_y, end_x, end_y, 0, -1);
            if (minstep < 1000)printf("pair %d: %d segments.\n", count, minstep);
            else printf("pair: %d: impossible.\n", count);
        }
        printf("\n");
    }




    return 0;
}