一锄贷、基本思想

二、 實(shí)例-小游戲

#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]; //定義標(biāo)記數(shù)組

//搜索函數(shù)
void Search(int now_x, int now_y, int end_x, int end_y, int step, int f) {
    if (step > minstep) {
        return;    //當(dāng)前路徑數(shù)大于minstep医咨， 返回->優(yōu)化策略
    }
    if (now_x == end_x && now_y == end_y) {   //到達(dá)終點(diǎn)
        if (minstep > step)  {   //更新最小路徑數(shù) 
            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;  //如果新位置冰沙，有效標(biāo)記該位置
            //上一步方向與當(dāng)前方向相同，則遞歸搜索時(shí)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();  //讀取緩存區(qū)中回車鍵
            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";
        }

        //在下方和右側(cè)添加空白
        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 ){
            //讀入起始點(diǎn)和終點(diǎn)
            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;
}

【相關(guān)文檔】
1.老生常談聪姿，正確使用memset
2.遞歸-小游戲（算法基礎(chǔ) 第3周）
3.Visual Studio 2012 編譯錯(cuò)誤【error C4996: 'scanf': This function or variable may be unsafe. 】的解決方案
4 深入了解scanf()/getchar()和gets()等函數(shù)