汪汪剪指甲 （C++代码）（ 深度优先搜索(DFS)入门题 ）

解题思路:

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

void DFS( 状态参数 ) {
	if ( 目的状态 ) {
	
		目的操作
		return;
	}

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

参考代码:

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

char Map[22][22];               /*    储存图    */
bool vis[22][22];               /* 标记走过的点 */
bool mark = false;              /*   目的标记   */
int map_width, map_high;        /*   图的长宽   */
int moveX[4] = { -1,0,1,0 };    /*   四个方向   */
int moveY[4] = { 0,-1,0,1 };

struct status {                 /* 记录当前位置 */
	int X, Y;
};

void DFS(int X, int Y) {

	/* 找到目标 - 标记 - 结束 */
	if (Map[X][Y] == 'T') {
		mark = true;
		return;
	}

	for (int i = 0; i < 4; i++) {
		status moving;
		/*    四个方向移动    */
		moving.X = X + moveX[i];
		moving.Y = Y + moveY[i];
		/*    判断边界条件    */
		/*    判断是否走过    */
		/*    判断是否障碍    */
		if (moving.X >= 0 && moving.Y >= 0 
			&& moving.X < map_high && moving.Y < map_width &&
			vis[moving.X][moving.Y] != true && Map[moving.X][moving.Y] != '#') {
			
			/*      标记走过      */
			vis[moving.X][moving.Y] = true;
			/*      深入搜索      */
			DFS(moving.X, moving.Y);
			/*         回溯       */
			vis[moving.X][moving.Y] = false;
		}
	}
}

int main() {
	int group;
	cin >> group;

	while (group--) {
		/*         读入图的数据        */
		cin >> map_high >> map_width; cin.get();
		for (int i = 0; i < map_high; i++) {
			gets(Map[i]);
		}

		
		bool start = false;
		/*      遍历图定位起点        */
		int position1, position2;
		for (position1 = 0; position1 < map_high; position1++) {
			for (position2 = 0; position2 < map_width; position2++)
				if (Map[position1][position2] == 'S') {
					start = true; break;
				}
			if (start == true) break;
		}
		/*  标记起点已走过。重置 mark */
		vis[position1][position2] = true; mark = false;

		/*      从起点开始进入搜索    */
		DFS(position1, position2);

		if (mark == true) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}