面试题 12. 矩阵中的路径

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

class Solution
{
public:
	bool exist(vector<vector<char>>& grid, const string& target )const
	{
		const int m=grid.size();    // 行数
		const int n=grid[0].size(); // 列数

		// index是字串target中单个字符的索引
		function<int(int,int,int)> dfs=[&](const int i,const int j,const int index)->int
		{
			if(index==target.length()){ return true; } // 如果目标单词的所有字母都找到了，返回 true
			// 越界检查及当前单元格字母是否匹配，或已经被访问过
			if(i<0||i>=m || j<0||j>=n || grid[i][j]!=target[index]){ return false;}

			// 标记当前位置为已访问
			const char tmp=grid[i][j];
			grid[i][j]='#';

			// 递归搜索四个方向：下、上、右、左
			const bool found = dfs(i+1,j,index+1) ||
				dfs(i-1,j,index+1) ||
				dfs(i,j+1,index+1) ||
				dfs(i,j-1,index+1);

			// 恢复当前位置
			grid[i][j]=tmp;

			return found;
		};


		// 遍历 grid 中的每个字符，作为起点开始 DFS
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if (dfs(i,j,0)) return true;
			}
		}
		return false;  // 如果所有路径都没有找到目标单词，返回 false
	}

};


int main()
{
	Solution solution;
	vector<vector<char>> grid = {
		{'A', 'B', 'C', 'E'},
		{'S', 'F', 'C', 'S'},
		{'A', 'D', 'E', 'E'}
	};
	string target = "ABCCED";

	if (solution.exist(grid, target)) {
		cout << "The word '" << target << "' exists in the grid.\n";
	} else {
		cout << "The word '" << target << "' does not exist in the grid.\n";
	}

	return 0;
}