2178: 信息学奥赛一本通T1255-迷宫问题 DFS

解题思路:DFS深搜 + 剪枝

注意事项:移动的顺序， 下右上左

参考代码:

#include<iostream>
#include<string>
#include<sstream>
#include<cstring>
using namespace std;
const int N = 1e1 + 10;
int g[N][N],dis[N][N],mx= 0x3f3f3f3f;
int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
bool v[N][N];
string m_path; 
void dfs(int x, int y, string path, int lth){
	if(x == 4 && y == 4){
		if(mx > lth) {
			m_path = path;
			mx = lth;
		}
		return;
	}
	if(dis[x][y] > lth) dis[x][y] = lth;
	else return;
	for(int i = 0 ; i < 4; i ++){
		int nx = d[i][0] + x;
		int ny = d[i][1] + y;
		if(nx >= 0 && nx < 5 && ny >=0 && ny < 5 && !g[nx][ny] && !v[nx][ny]){
			v[nx][ny] = true;
			stringstream ss;
			ss << path << "\n(" <<nx <<", "<<ny<<")";
			dfs(nx,ny,ss.str(),lth + 1);
			v[nx][ny] = false;
		} 
	}
	
}
int main()
{
	memset(dis, 0x3f, sizeof(dis));
	for(int i = 0; i < 5; i ++)
		for(int j = 0; j < 5; j ++)
			cin >> g[i][j];
	string s = "(0, 0)";
	dfs(0,0,s,0);
	cout << m_path;
	return 0;
}