牛客题霸 -- HJ43 迷宫问题

在这里插入图片描述
解题步骤;

参考代码：

//最短路径下标
vector<vector<int>> MinPath;
//临时路径
vector<vector<int>> tmp;
int row = 0;
int col = 0;
void FindMinPath(vector<vector<int>>& nums, int i, int j)
{
	nums[i][j]=1;
	tmp.push_back({i,j});

	//说明这条路径已经走通
	if(i==row-1&&j==col-1)
	{
		//第一次，即MinPath.size()==0时也要给MinPath赋值
		//否则最终的MinPath就会等于0了
		if(MinPath.size()==0||tmp.size()<MinPath.size())
		{
			MinPath=tmp;
		}
		return;
	}

	//无论是向哪个方向走，都必须要确保这个方向的位置能走，
	//保证不越界并且这个方向的值不为1，否则就不能走
	//向上
	if(i-1>=0&&nums[i-1][j]==0)
	{
		FindMinPath(nums,i-1,j);
	}
	//向下
	if(i+1<row&&nums[i+1][j]==0)
	{
		FindMinPath(nums,i+1,j);
	}
	//向左
	if(j-1>=0&&nums[i][j-1]==0)
	{
		FindMinPath(nums,i,j-1);
	}
	//向右
	if(j+1<col&&nums[i][j+1]==0)
	{
		FindMinPath(nums,i,j+1);
	}

	//经过该点的四个方向都已经走过了，此时应该回溯，即
	//把这个点从tmp中删除掉，并把该点的值恢复为原来的0，
	//因为原来一定是0，如果原来是1是不会进来这一层递归的
	tmp.pop_back();
	nums[i][j]=0;

}


int main()
{
	cin>>row>>col;
	vector<vector<int>> nums(row,vector<int>(col));
	for(int i=0;i<row;i++)
	{
		for(int j=0;j<col;j++)
		{
			cin>>nums[i][j];
		}
	}
	FindMinPath(nums,0,0);
	for(int i=0;i<MinPath.size();i++)
	{
		cout<<"("<<MinPath[i][0]<<","<<MinPath[i][1]<<")"<<endl;
	}
	return 0;
}