搜索专题

之前虽然学过搜索，感觉忘了很多，所以写一遍博客来回忆一下。

深度优先搜索（DFS)和广度优先搜索(BFS)是基本的暴力技术。

一般来说用队列这种数据结构来实现BFS,用栈这种数据结构来实现DFS（用递归来实现)。

经典BFS：

贴一个🔗http://lx.lanqiao.cn/problem.page?gpid=T291

AC代码：

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

int m, n;
int maze[505][505];
bool vis[505][505];
//下左右上 
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char r[4] = {'D', 'L', 'R', 'U'};

struct node {
	int x;
	int y;
	int step;
	string road;
};

bool check(int x, int y) {
	if(x >= 0 && x < n  && y >= 0 && y < m && !vis[x][y] && maze[x][y] == 0) 
		return true;
	return false;
}

void BFS(int x, int y) { 
	queue <node> q;
	node st, ne;
	st.x = x;
	st.y = y;
	st.step = 0;
	st.road = "";
	vis[x][y] = true;
	q.push(st);
	while(!q.empty()) {
		st = q.front();
		q.pop();
		if(st.x == n - 1 && st.y == m - 1) {
			cout << st.step << endl << st.road << endl;
			return;
		}
		for(int i = 0; i < 4; ++i) {
			ne.x = st.x + dir[i][0];
			ne.y = st.y + dir[i][1];
			if(check(ne.x, ne.y)) {
				vis[ne.x][ne.y] = true;
				ne.step = st.step + 1;
				ne.road = st.road + r[i];
				q.push(ne);
			}
		}
	}
}


int main() {
	cin >> n >> m;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
            //这个地方我感觉还是有点坑的，测试数据连续输入不加空格
			scanf("%1d", &maze[i][j]);
		}
	}
	BFS(0, 0);
	return 0;
}