c++回溯法编程汇总

灰太狼 2024-04-18 19:10 88阅读 0赞

回溯算法的定义：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

*      递归函数的开头写好中止条件，或者跳出条件，满足条件才将当前结果加入总结果中，或者不满足让函数return，防止重复遍历
 *      已经经过的地点不在经过(已经搜索过的解空间不再重复搜索)
 *      遍历过当前节点后，为了回溯到上一步，要去掉已经加入到结果list中的当前节点。

**目录**

一、矩阵中的路径

1.1 题干

二、矩阵中的递增路径

1.1 题干

1.2 思路及代码

三、不同路径

3.1 题干

3.2 分析

3.2 障碍物的不同路径

3.3 思路及解法

四、N皇后问题

4.1 题干

4.2 分析

五、数独解

5.1 题干

5.2 分析

六、推箱子

6.1 题干

6.2 思路及程序

--------------------

# 一、矩阵中的路径 #

OJ：[https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_c61c6999eecb4b8f88a98f66b273a3cc_tpId_13_tqId_11218_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

## 1.1 题干 ##

例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bccced"的路径，但是矩阵中不包含"abcb"路径，判断是否存在，存在返回true，不存在返回false

![20190910213122523.png][]

1.2 思路

遍历，进行匹配

*  依次从每个位置出发，与匹配的路径进行对比
 *  设置bool矩阵，尺寸大小与矩阵相同，已经经过的位置，则将bool中的值设置为true，防止重复经过
 *  不想被改变的量，我们可以加上const修饰，以免不小心将其改变，如果改变const的变量，编译器会报错
 *  经过的矩阵以对于moving中的reached矩阵，不要加引用&，因为这样，每调用一次，会重新传递参数给相应的函数。
 *  此代码在每次进入下次函数递归的时候加判断，可能会导致代码不够精简。如果直接可以在每次函数开始之前加判断，可能能够精简代码。因此，我们可以重新编写函数。

#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stdio.h>
    #include<algorithm>
    using namespace std;
    
    class Solution {
    public:
    	bool hasPath(char* matrix, int rows, int cols, const char* str)
    	{
    		bool exist = false;
    		int length = strlen(str);
    		for (int idx_r = 0; idx_r < rows; idx_r++){
    			for (int idx_c = 0; idx_c < cols; idx_c++){
    				vector<bool> reached(rows*cols, false);
    				exist = exist || (moving(matrix, idx_r, idx_c, rows, cols, str, reached, 0, length));
    				if (exist)return true;
    			}
    		}
    		return exist;
    	}
    	bool moving(const char* matrix, int cur_r, int cur_c, int rows, int cols,
    		const char* str, vector<bool> reached, int str_loc, const int length){
    		int location = cur_r*cols + cur_c;
    		if (matrix[location] != str[str_loc])return false;//不相等则此路径不存在
    		else if (str_loc == length - 1){//余下情况是可能存在路径的情况
    			//如果已经到了str的结尾，则路径存在，return true
    			return true;
    		}
    		//如果没有到str结尾，则接着往下比较
    		reached[location] = true;//关于reached矩阵，相当于每个往函数里面都复制了一份，千万不要用引用&，而要直接传入
    		bool exist = false;
    		// right
    		int right = cur_r*cols + cur_c + 1;
    		if (cur_c + 1 < cols && !reached[right]){
    			exist = exist || (moving(matrix, cur_r, cur_c + 1, rows, cols, str, reached, str_loc + 1, length));
    		}
    		// left
    		int left = cur_r*cols + cur_c - 1;
    		if (cur_c - 1 >= 0 && !reached[left]){
    			exist = exist || (moving(matrix, cur_r, cur_c - 1, rows, cols, str, reached, str_loc + 1, length));
    		}
    		// up
    		int up = (cur_r + 1)*cols + cur_c;
    		if (cur_r + 1 < rows && !reached[up]){
    			exist = exist || (moving(matrix, cur_r + 1, cur_c, rows, cols, str, reached, str_loc + 1, length));
    		}
    		//down
    		int down = (cur_r - 1)*cols + cur_c;
    		if (cur_r - 1 >= 0 && !reached[down]){
    			exist = exist || (moving(matrix, cur_r - 1, cur_c, rows, cols, str, reached, str_loc + 1, length));
    		}
    		return exist;
    	}
    };
    
    int main(){
    	char *matrix = "abcesfcsadee";
    	int rows = 3; int cols = 4;
    	char *str1 = "bcced";  // true
    	char *str2 = "abcb";  // false
    	Solution s1;
    	cout << s1.hasPath(matrix, rows, cols, str1) << endl;//true
    	cout << s1.hasPath(matrix, rows, cols, str2) << endl;//true
    	int end; cin >> end;
    	return 0;
    }

下面的代码，先判断，后递归，从代码量上已经下降很多：

class Solution {
    public:
    	bool hasPath(char* matrix, int rows, int cols, const char* str)
    	{
    		bool exist = false;
    		int length = strlen(str);
    		for (int idx_r = 0; idx_r < rows; idx_r++){
    			for (int idx_c = 0; idx_c < cols; idx_c++){
    				vector<bool> reached(rows*cols, false);
    				exist = exist || (moving(matrix, idx_r, idx_c, rows, cols, str, reached, 0, length));
    				if (exist)return true;
    			}
    		}
    		return exist;
    	}
    	bool moving(const char* matrix, int cur_r, int cur_c, int rows, int cols,
    		const char* str, vector<bool> reached, int str_loc, const int length){
    		int location = cur_r*cols + cur_c;
    		if (cur_r<0 || cur_r >= rows || cur_c<0 || cur_c >= cols || reached[location] == true || matrix[location] != str[str_loc])return false;//不相等则此路径不存在
    		else if (str_loc == length - 1){//余下情况是可能存在路径的情况
    			//如果已经到了str的结尾，则路径存在，return true
    			return true;
    		}
    		//如果没有到str结尾，则接着往下比较
    		reached[location] = true;//关于reached矩阵，相当于每个往函数里面都复制了一份，千万不要用引用&，而要直接传入
    		bool exist = false;
    		// right
    		exist = exist || (moving(matrix, cur_r, cur_c + 1, rows, cols, str, reached, str_loc + 1, length));
    		// left
    		exist = exist || (moving(matrix, cur_r, cur_c - 1, rows, cols, str, reached, str_loc + 1, length));
    		// up
    		exist = exist || (moving(matrix, cur_r + 1, cur_c, rows, cols, str, reached, str_loc + 1, length));
    		//down
    		exist = exist || (moving(matrix, cur_r - 1, cur_c, rows, cols, str, reached, str_loc + 1, length));
    		return exist;
    	}
    };

# 二、矩阵中的递增路径 #

## 1.1 题干 ##

2019.9.7 依图面试，当时面试的时候，list不小心弄成了&list，导致运行失败。但是思路基本没有错误。事后马上就编写出来了。

输出最长递减序列路径以及路径中的最后一个元素的位置：

给定一个矩阵，输入

{ 1, 2, 3 },
    { 4, 5, 6 }，
    { 9, 0, 8 }

输出其最长递减的子字符串的长度和第一个元素的位置

输出2,2 5最长路径的起点是8，其位置为2,2

## 1.2 思路及代码 ##

*  用list存当前路径，如果存不下，则list中止，存入全局变量all\_list之中。
 *  如果存得下，就继续往下递归

#include <iostream>
    #include<vector>
    using namespace std;
    
    int row;
    int col;
    void moving(int loc_r, int loc_c, vector<vector<int>> matrix, vector<int> list, vector<vector<int>>&all_list){
    	list.push_back(matrix[loc_r][loc_c]);
    
    	bool exist = false;
    	// down
    	if ((loc_r + 1< ::row) && matrix[loc_r + 1][loc_c]>list[list.size() - 1]){
    		exist = true;
    		moving(loc_r + 1, loc_c, matrix, list, all_list);
    	}
    	//up
    	if (loc_r - 1 >= 0 && matrix[loc_r - 1][loc_c]>list[list.size() - 1]){
    		exist = true;
    		moving(loc_r - 1, loc_c, matrix, list, all_list);
    	}
    	//left
    	if (loc_c - 1 >= 0 && matrix[loc_r][loc_c - 1]>list[list.size() - 1]){
    		exist = true;
    		moving(loc_r, loc_c - 1, matrix, list, all_list);
    	}
    	//right 
    	if (loc_c + 1< ::col && matrix[loc_r][loc_c + 1]>list[list.size() - 1]){
    		exist = true;
    		moving(loc_r, loc_c + 1, matrix, list, all_list);
    	}
    	if (!exist){
    		list.push_back(loc_r);
    		list.push_back(loc_c);
    		all_list.push_back(list);
    		//list.clear();
    		return;
    	}
    }
    int main() {
    	vector<vector<int>>matrix{ { 1, 2, 3 }, { 4, 5, 6 }, { 9, 0, 8 } };
    	row = matrix.size();
    	col = matrix[0].size();
    	vector<int> list;
    	vector<vector<int>>all_list;
    	for (int idx = 0; idx<row; idx++){
    		for (int idx_c = 0; idx_c<col; idx_c++){
    			moving(idx, idx_c, matrix, list, all_list);
    		}
    	}
    	int max_len = -2;
    	int last_row, last_col;
    	for (auto item : all_list){
    		cout << "max_len " << max_len << " size-2 " << item.size() - 2 << endl;
    		int length = item.size() - 1;
    		if (length > max_len){
    			cout << "in if max_len " << max_len << " size-2 " << item.size() - 2 << endl;
    			max_len = item.size() - 2;
    			last_row = item[item.size() - 2];
    			last_col = item[item.size() - 1];
    		}
    	}
    	cout << last_row << ',' << last_col << " " << max_len << endl;
    	int end; cin >> end;
    	return 0;
    }

# 三、不同路径 #

## 3.1 题干 ##

LeetCode 980,OJ:

[https://leetcode-cn.com/problems/unique-paths-iii/][https_leetcode-cn.com_problems_unique-paths-iii]

在二维网格 grid 上，有 4 种类型的方格：

*      1 表示起始方格。且只有一个起始方格。
 *      2 表示结束方格，且只有一个结束方格。
 *      0 表示我们可以走过的空方格。
 *      -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。即012的方格，**必须且有且只有通过一次**，-1的方格不能经过。

输入：\[\[1,0,0,0\],\[0,0,0,0\],\[0,0,2,-1\]\]

输出：2

## 3.2 分析 ##

又是典型的走迷宫问题。需要回归的是走法的方法数目。

设置递归函数：

*  设置已经经过的路径用vector<vector<bool>>passed来实现
 *  如果-1，则return false;表明此路径失败，不存在
 *  如果是2，则表示运行到终点，如果每个0的点都经过了，则此路径运行成功

#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stdio.h>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    class Solution {
    public:
    	int uniquePathsIII(vector<vector<int>>& grid) {
    		int row = grid.size();
    		if (row < 1)return 0;
    		int col = grid[0].size();
    		if (col < 1)return 0;
    		//设置经过的位置的矩阵，经过则设为passed
    		vector<bool>passed_col(col, false);
    		vector<vector<bool>>passed(row, passed_col);
    		int methods = 0;
    		for (int r = 0; r < row; r++){
    			for (int c = 0; c < col; c++){
    				if (grid[r][c] == 1){
    					moving(row, col, grid, methods, r, c, passed);
    				}
    			}
    		}
    		return methods;
    	}
    	void moving(const int row, const int col, const vector<vector<int>>& grid,
    		int &methods, int cur_r, int cur_c, vector<vector<bool>>passed){
    		//走出格子之外，或者碰壁-1，或者走回头路，则直接返回
    		if (cur_r >= row || cur_r<0 || cur_c >= col || cur_c < 0 || grid[cur_r][cur_c] == -1 || passed[cur_r][cur_c]){
    			return;
    		}
    		//成功走到终点2,且每个都经过了一次，经过的方法数目+1
    		if (grid[cur_r][cur_c] == 2){
    			//判断是否经过的0或者1均经过，如果不是的话，则直接返回
    			for (int r = 0; r < row; r++){
    				for (int c = 0; c < col; c++){
    					if (grid[r][c] == 0 || grid[r][c] == 1){
    						if (!passed[r][c]){
    							return;
    						}
    					}
    				}
    			}
    			methods++;
    			return;
    		}
    		// 如果其他情况，则继续往下走
    		if (grid[cur_r][cur_c] == 0 || grid[cur_r][cur_c] == 1){
    			passed[cur_r][cur_c] = true;
    			moving(row, col, grid, methods, cur_r + 1, cur_c, passed);
    			moving(row, col, grid, methods, cur_r - 1, cur_c, passed);
    			moving(row, col, grid, methods, cur_r, cur_c + 1, passed);
    			moving(row, col, grid, methods, cur_r, cur_c - 1, passed);
    		}
    	}
    };
    
    int main(){
    
    	vector<vector<int>> grid = { { 1, 0, 0, 0 },
    	{ 0, 0, 0, 0 }, { 0, 0, 2, -1 } };// out 2
    	vector<vector<int>> grid2 = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 2 } };//out 4
    
    	Solution s1;
    	cout << s1.uniquePathsIII(grid) << endl;
    	cout << s1.uniquePathsIII(grid2) << endl;
    
    	int end; cin >> end;
    	return 0;
    }

## 3.2 障碍物的不同路径 ##

机器人希望从左上角到右下角，中间有障碍物。只能向左或者向下走，问有多少种走法？障碍物在矩阵中用1表示。

输入[
      [0,0,0],
      [0,1,0],
      [0,0,0]]
    输出: 2

## 3.3 思路及解法 ##

动态规划方法

*  很简单，可以看作动态规划，当前路径为左边和上边的路径数
 *  如果当前为1，障碍物，则路径必不存在，则当前方法数目为0

#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<stdio.h>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    class Solution {
    public:
    	int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    		int row = obstacleGrid.size();
    		if (row < 1)return 0;
    		int col = obstacleGrid[0].size();
    		if (col < 1)return 0;
    		if (obstacleGrid[0][0] == 1)return 0;
    		vector<unsigned long long int> col_methods(col, 0);
    		vector<vector<unsigned long long int>>methods(row, col_methods);
    		//到每一点的方法数目
    		methods[0][0] = 1;
    		//第一列,行的方法数目
    		for (int idx = 1; idx < row; idx++){
    			if (obstacleGrid[idx][0] == 1)methods[idx][0] = 0;
    			else{
    				methods[idx][0] = methods[idx - 1][0];
    			}
    		}
    		for (int idx = 1; idx < col; idx++){
    			if (obstacleGrid[0][idx] == 1)methods[0][idx] = 0;
    			else{
    				methods[0][idx] = methods[0][idx - 1];
    			}
    		}
    		//每一个位置的方法数目是其左边和上边方法数的和
    		for (int r = 1; r < row; r++){
    			for (int c = 1; c < col; c++){
    				if (obstacleGrid[r][c] == 1)methods[r][c] = 0;
    				else{
    					methods[r][c] += methods[r - 1][c] + methods[r][c - 1];
    				}
    			}
    		}
    		return methods[row - 1][col - 1];
    	}
    };
    
    int main(){
    	vector<vector<int>> grid = { { 0, 0, 0 },
    	{ 0, 1, 0 }, { 0, 0, 0 } };// out 2
    	Solution s1;
    	cout << s1.uniquePathsWithObstacles(grid) << endl;
    	int end; cin >> end;
    	return 0;
    }

# 四、N皇后问题 #

N皇后问题，Leetcode 51

OJ：[https://leetcode-cn.com/problems/n-queens/][https_leetcode-cn.com_problems_n-queens]

## 4.1 题干 ##

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。即这N个皇后不能同行同列同斜列。

输入，棋盘，输出放置的方法：
    输入: 4
    输出: [
     [".Q..",  // 解法 1
      "...Q",
      "Q...",
      "..Q."],
    
     ["..Q.",  // 解法 2
      "Q...",
      "...Q",
      ".Q.."]]

## 4.2 分析 ##

看作回溯法的问题：

*  每行找到一个元素，放置之后，如果可以的话往下一个行放
 *  每行放入的时候，如果满足条件，才往下一行放，不满足则不放
 *  到结尾的时候，满足条件则对最终结果push\_back
 *  用每行的列位置来存储，则能简化存储与运算。最后再恢复出来

代码：

#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<set>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    class Solution {
    public:
    	vector<vector<string>> solveNQueens(int n) {
    		vector<vector<string>> result_matrix;
    		if (n < 1)return result_matrix;
    		vector<int> col_loc(n);// col[idx=row],一共n列
    		vector<vector<int>>result; //用于存储所有满足条件的位置的集合
    		find_location(n, 0, col_loc, result);
    
    		if (result.empty())return result_matrix;
    		else{//根据行列值恢复出皇后矩阵
    			for (auto item : result){
    				string each_row(n, '.');
    				vector<string> matrix(n, each_row);//空矩阵
    				for (int idx = 0; idx < n; idx++){//填入皇后
    					matrix[idx][item[idx]] = 'Q';
    				}
    				result_matrix.push_back(matrix);
    			}
    		}
    		return result_matrix;
    	}
    	//判断当前row位置的元素是否与其他元素(<row)冲突
    	bool judge_correct(const int n, const int row, const vector<int> col_loc){
    		for (int idx = 0; idx < row; idx++){
    			if (col_loc[idx] == col_loc[row])return false;//列不能相等
    			if (idx + col_loc[idx] == row + col_loc[row])return false;//右上、左下不冲突
    			if (idx - col_loc[idx] == row - col_loc[row])return false;//左上，右下不冲突
    		}
    		return true;
    	}
    	//给当前row位置元素判断
    	void find_location(const int n, int row, vector<int> col_loc, vector<vector<int>> &result){
    		//如果已经到最后一行，可以加入则将元素加入之后返回
    		if (row == n - 1){
    			for (int idx = 0; idx < n; idx++){
    				col_loc[row] = idx;
    				if (judge_correct(n, row, col_loc)){
    					result.push_back(col_loc);
    				}
    			}
    			return;
    		}
    		//如果没有到最后一行，则加入元素之后进行递归
    		for (int idx = 0; idx < n; idx++){
    			col_loc[row] = idx;
    			if (judge_correct(n, row, col_loc)){
    				find_location(n, row + 1, col_loc, result);
    			}
    		}
    	}
    };
    
    int main(){
    	Solution s1;
    	vector<vector<string>> result_matrix = s1.solveNQueens(4);
    
    	if (result_matrix.empty())cout << "Empty!" << endl;
    	else{
    		for (auto matrix : result_matrix){
    			cout << endl << "matrix:" << endl;
    			for (auto row_string : matrix){
    				cout << row_string << endl;
    			}
    		}
    	}
    
    
    	int end; cin >> end;
    	return 0;
    }

# 五、数独解 #

OJ：Leetcode 37

[https://leetcode-cn.com/problems/sudoku-solver/][https_leetcode-cn.com_problems_sudoku-solver]

## 5.1 题干 ##

将数独填完：

*      数字 1-9 在每一行只能出现一次。
 *      数字 1-9 在每一列只能出现一次。
 *      数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70][]

输入：
    53..7....
    6..195...
    .98....6.
    8...6...3
    4..8.3..1
    7...2...6
    .6....28.
    ...419..5
    ....8..79
    输出
    534678912
    672195348
    198342567
    859761423
    426853791
    713924856
    961537284
    287419635
    345286179

![20190910213805565.png][]

## 5.2 分析 ##

*  针对每一个元素进行填充，如果符合规矩，则继续向下递归填充下一个未填充的元素
 *  当前元素填充试过所有的，即进行return
 *  运行超时，电脑上运行发现程序没有错误，但是运行较慢，下面代码是暴力穷举法，显然不行，必须加入约束条件进行判断

#include<iostream>
    #include<vector>
    #include<cstdio>
    #include<set>
    #include<string>
    #include<algorithm>
    using namespace std;
    
    class Solution {
    public:
    	void solveSudoku(vector<vector<char>>& board) {
    		vector<vector<char>>result;
    		find_sudoku(board, result);
    		board = result;
    	}
    	//判断新加入元素是否符合
    	bool num_match(const vector<vector<char>> board, const int row, const int col){
    		for (int idx = 0; idx < 9; idx++){
    			//行不同
    			if (idx != col){
    				if (board[row][col] == board[row][idx])return false;
    			}
    			//列不同
    			if (idx != row){
    				if (board[row][col] == board[idx][col])return false;
    			}
    		}
    		//每个九宫格内不同
    		int grid_row = row / 3; int grid_col = col / 3;
    		for (int r = 3 * grid_row; r < 3 * grid_row + 3; r++){
    			for (int c = 3 * grid_col; c < 3 * grid_col + 3; c++){
    				if (r != row || c != col){
    					if (board[r][c] == board[row][col])return false;
    				}
    
    			}
    		}
    		return true;
    	}
    	void find_sudoku(vector<vector<char>> board, vector<vector<char>> &result){
    		int row = 0; int col = 0;
    		for (row = 0; row < 9; row++){
    			for (col = 0; col < 9; col++){
    				//遍历每一行每一列，找到新的未填充的元素
    				if (board[row][col] == '.'){
    					//给每个元素填入相应的值，判断能否合规
    					for (int idx = 1; idx <= 9; idx++){
    						board[row][col] = '0' + idx;
    						//填充值恰当则继续往下填充
    						if (num_match(board, row, col)){
    							find_sudoku(board, result);
    						}
    					}
    					return;//需要在当前元素填充结束之后，结束当前遍历。
    				}
    			}
    		}
    		if (row == 9 && col == 9)result = board;
    	}
    };
    
    int main(){
    	vector<char>each_row(9);
    	vector<vector<char>> board(9, each_row);
    
    	/*
    	53..7....
    	6..195...
    	.98....6.
    	8...6...3
    	4..8.3..1
    	7...2...6
    	.6....28.
    	...419..5
    	....8..79
    	*/
    	for (int row = 0; row < 9; row++){
    		for (int col = 0; col < 9; col++){
    			cin >> board[row][col];
    		}
    	}
    
    	Solution s1;
    	s1.solveSudoku(board);
    	//输出矩阵
    	for (int row = 0; row < 9; row++){
    		for (int col = 0; col < 9; col++){
    			cout << board[row][col];
    		}
    		cout << endl;
    	}
    
    	int end; cin >> end;
    	return 0;
    }

# 六、推箱子 #

## 6.1 题干 ##

体规则就是在一个N\*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。

输入描述:

*      每个测试输入包含1个测试用例
 *      第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
 *      接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、\*表示箱子、\#表示障碍、@表示目的地。
 *      每个地图必定包含1个玩家、1个箱子、1个目的地。

输出描述:

输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。

4 4
    ....
    ..*@
    ....
    .X..
    输出3
    
    ...#..
    ......
    #*##..
    ..##.#
    ..X...
    .@#...
    输出11
    
    1 3
    X*@
    输出1

## 6.2 思路及程序 ##

思路：

*  一个记录当前人和箱子位置的变量
 *  如果溢出或者撞墙，则return
 *  如果没有溢出或者没有撞墙，则继续往下
 *  人和箱子挨着且与方向一致则推箱子，不一致人自己走
 *  运算复杂度较高，运行一次耗时较长

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include<string>
    
    using namespace std;
    int row, col;
    int moves = -1;
    void moving(int r, int c, int br, int bc, int current_moves,
    	const vector<vector<char>> matrix, vector<vector<bool>>p_reach){
    	
    	// 运行失败
    	if (r < 0 || r >= row || c < 0 || c >= col || p_reach[r][c] == true || matrix [r][c]=='#'||
    		br < 0 || br >= row || bc < 0 || bc >= col || matrix[br][bc]=='#'){
    		//cout << "fail" << endl;
    		return;
    	}
    
    	 输出当前矩阵状态
    	//cout << endl;
    	//for (int idx = 0; idx < row; idx++){
    	//	for (int cdx = 0; cdx < col; cdx++){
    	//		if (idx == r && cdx == c)cout << 'X';
    	//		else if (idx == br && cdx == bc)cout << '*';
    	//		else cout << matrix[idx][cdx];
    	//	}
    	//	cout << endl;
    	//}
    
    	//运行成功
    	if (matrix[br][bc] == '@'){
    		if (moves == -1)moves = current_moves;
    		else if (current_moves < moves){
    			//cout << "success,current:"<<current_moves<<"moves:"<<moves << endl;
    			moves = current_moves;
    		}
    		return;
    	}
    	current_moves++;
    	p_reach[r][c] = true; 
    	//推或者走
    	// down
    	if (r + 1 == br && c == bc)moving(r + 1, c, br + 1, bc, current_moves, matrix, p_reach);
    	else moving(r + 1, c, br, bc, current_moves, matrix, p_reach);
    	//up
    	if (r - 1 == br && c == bc)moving(r - 1, c, br - 1, bc, current_moves, matrix, p_reach);
    	else moving(r - 1, c, br, bc, current_moves, matrix, p_reach);
    	//right
    	if (r  == br && c+1 == bc)moving(r , c+1, br , bc+1, current_moves, matrix, p_reach);
    	else moving(r , c+1, br, bc, current_moves, matrix, p_reach);
    	//left
    	if (r == br && c - 1 == bc)moving(r, c - 1, br, bc- 1, current_moves, matrix, p_reach);
    	else moving(r, c - 1, br, bc, current_moves, matrix, p_reach);
    	return;
    }
    
    int main(){
    	cin >> row >> col;
    	vector<char> each_row(col);
    	vector<vector<char>>matrix(row, each_row);
    	for (int r = 0; r < row; r++){
    		for (int c = 0; c < col; c++){
    			cin >> matrix[r][c];
    		}
    	}
    	vector<bool> r_reach(col, false);
    	vector<vector<bool>>p_reach(row, r_reach);
    	int pr, pc, br, bc;
    	for (int r = 0; r < row; r++){
    		for (int c = 0; c < col; c++){
    			if (matrix[r][c] == 'X'){
    				pr = r; pc = c;
    			}
    			if (matrix[r][c] == '*'){
    				br = r; bc = c;
    			}
    		}
    	}
    	moving(pr, pc, br, bc, 0, matrix,p_reach);
    
    	cout << ::moves << endl;
    
    	int end; cin >> end;
    	return 0;
    }

[https_www.nowcoder.com_practice_c61c6999eecb4b8f88a98f66b273a3cc_tpId_13_tqId_11218_tPage_4_rp_4_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/c61c6999eecb4b8f88a98f66b273a3cc?tpId=13&tqId=11218&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[20190910213122523.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/bff844e1a9154a6398676ea3c85a125b.png
[https_leetcode-cn.com_problems_unique-paths-iii]: https://leetcode-cn.com/problems/unique-paths-iii/
[https_leetcode-cn.com_problems_n-queens]: https://leetcode-cn.com/problems/n-queens/
[https_leetcode-cn.com_problems_sudoku-solver]: https://leetcode-cn.com/problems/sudoku-solver/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjQ3NDgwOQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d6a90fa55f634feab0c9af339ee44a7c.png
[20190910213805565.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2a6dacb86d91445e9ac65fc4acbdeaf1.png