80分求调cpp dfs
查看原帖
80分求调cpp dfs
802998
qpy19862511760楼主2024/4/10 00:26

#include<iostream>
using namespace std;
#include<vector>
int n, m;
int vis[16][16];
int dx[4] = { 0,-1,0,1 }; 
int dy[4] = { -1,0,1,0 };
void dfs(vector<string>& pathRet, vector<vector<int> >& maze, int x, int y, int ex, int ey, string& path) {

	if (x < 0 || y < 0 || x >= m || y >= n)
		return; 
	if (vis[x][y])
		return; 
	if (maze[x][y] == 0)
		return; 
	if (x == ex && y == ey)
	{
		path += "(";
		path.push_back(1 + x + '0'); 
		path += ",";
		path.push_back(1 + y + '0');
		path += ")";
		pathRet.push_back(path);
		while (path[path.size() - 1] != '(')
			path.erase(path.end() - 1);
		if (!path.empty())
			path.erase(path.end() - 1);
		return;
	}
	vis[x][y] = 1;
	path += "(";
	path.push_back(x + 1 + '0');
	path += ",";
	path.push_back(y + 1 + '0'); 
	path += ")";
	path += "->";
	for (int i = 0; i < 4; i++) {
		int nx, ny; 
		nx = x + dx[i]; 
		ny = y + dy[i];
		dfs(pathRet, maze, nx, ny, ex, ey, path);
	}
	vis[x][y] = 0;
	while (path[path.size() - 1]!= '(')
		path.erase(path.end() - 1);
	if (!path.empty())
		path.erase(path.end() - 1); 
	return;
}
int main(){
	cin >> m >> n;
	int sx, sy, ex, ey;
	vector<vector<int>>maze;
	maze.resize(m);
	for (int i =0; i < m; i++)
	{
		maze[i].resize(n);
		for (int j = 0; j < n; j++)
		{
			int val;
			cin >> val;
			maze[i][j] = val;
		}
	}
	vector<string> pathRet;
	string path = "";
	cin >> sx >> sy >> ex >> ey;
	dfs(pathRet, maze, sx - 1, sy - 1, ex - 1, ey - 1, path);
	if (pathRet.size() == 0)
		cout << -1;
	else {
		for (int i = 0; i < pathRet.size(); i++)
			cout << pathRet[i] << endl;
	}
	return 0;
};

2024/4/10 00:26
加载中...