蓝桥杯2015年第六届真题-穿越雷区 （C++代码）

解题思路:

        DFS 核心代码，根据题意添加操作。

void DFS( 状态参数 ) {
    if ( 目的状态 ) {
     
        目的操作
        return;
    }
 
    for ( 搜索方式(移动) )
    {
        if ( 合法状态 ) {
         
            操作
            标记
             
            DFS（ 更新状态参数 ）
             
            回溯 ( 还原标记 )
        }
    }
}

注意事项:

        因为行字符间格了空格，所有沿着行搜索的时候步数需要 +2 个单位。

参考代码:

#include<bits/stdc++.h>
using namespace std;

char Map[105][105];              /*      保存图      */
bool vis[105][105] = { false };  /*   标记走过的点   */
int  map_size;                   /*     方阵大小     */
int  moveX[4] = { -1,0,1,0 };    /* 每一步移动的距离 */
int  moveY[4] = { 0,-2,0,2 };
int  minstep = 9999;

struct status {                  /*   保存当前位置   */
	int X, Y;
};

void DFS(int X, int Y, int step) {
	/*       走到出口比较步数       */
	if (Map[X][Y] == 'B') {
		if (step < minstep) minstep = step;
		return;
	}

	for (int i = 0; i < 4; i++) {
		status moving;
		/*      四个方向搜索        */
		moving.X = X + moveX[i];
		moving.Y = Y + moveY[i];
		/*         判断边界         */
		/*       判断是否走过       */
		/*       判断字符异同       */
		/* 特别注意Y < 2 * map_size */
		if (moving.X >= 0 && moving.Y >= 0 && moving.X < map_size &&
			moving.Y < map_size * 2 && vis[moving.X][moving.Y] != true &&
			Map[moving.X][moving.Y] != Map[X][Y]) {

			vis[moving.X][moving.Y] = true;
			DFS(moving.X, moving.Y, step + 1);
			/*       回溯状态       */
			vis[moving.X][moving.Y] = false;
		}
	}
}

int main() {
	cin >> map_size; cin.get();
	for (int i = 0; i < map_size; i++) {
		gets(Map[i]);
	}
	bool start = false;

	/*         寻找起点位置         */
	int position1, position2;
	for (position1 = 0; position1 < map_size; position1++) {
		for (position2 = 0; position2 < map_size; position2++)
			if (Map[position1][position2] == 'A') {
				start = true; break;
			}
		if (start == true) break;
	}
	/*             搜索             */
	vis[position1][position2] = true;
	DFS(position1, position2, 0);

	if (minstep == 9999) cout << -1 << endl;
	else cout << minstep << endl;
}