感觉类似BFS，可以参考acwing出现的题目：AcWing 844. 走迷宫 – AcWing

贴上上面这道题的BFS暴力模板：

#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int N = 105;
int g[N][N];
int dist[N][N];
int n, m;
typedef pair<int, int> PII;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void bfs(int x, int y) //起点
{
	queue<PII>Q;
	Q.push({x, y});
	while (!Q.empty())
	{
		auto t = Q.front();
		Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int curx = t.first + dx[i];
			int cury = t.second + dy[i];
			if (curx <= 0 || curx > n || cury <= 0 || cury > m)
			{
				continue;
			}
			else
			{
				if (g[curx][cury] == 0)
				{
					Q.push({curx, cury});
					dist[curx][cury] = dist[t.first][t.second] + 1;
					g[curx][cury]++;
				}
			}
		}
	}

}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> g[i][j];
		}
	}
	bfs(1, 1);
	cout << dist[n][m];
	return 0;
}

这题用BFS求解会比较慢，力扣上过了87/89个用例，代码如下：

class Solution {
public:
    int row;
    int col;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        row = grid.size();
        if(row == 0) return false;
        col = grid[0].size();
        if(target.empty()) return true;

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                // bfs入口是第一个字符匹配的地方
                if(grid[i][j] == target[0]) {
                    if(bfs(grid, target, i, j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool bfs(vector<vector<char>>& grid, string target, int x, int y) {
        queue<tuple<int, int, int, vector<vector<bool>>>> q;
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        visited[x][y] = true;
        q.push({x, y, 1, visited});

        while(!q.empty()) {
            auto [i, j, pos, vis] = q.front();
            q.pop();

            // 如果pos==target.size 说明找到了匹配项
            if(pos == target.size()) {
                return true;
            }

            for(int k = 0; k < 4; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(ni >= 0 && ni < row && nj >= 0 && nj < col && !vis[ni][nj] && grid[ni][nj] == target[pos]) {
                    auto newVis = vis;
                    newVis[ni][nj] = true;
                    q.push({ni, nj, pos + 1, newVis});
                }
            }
        }
        return false;
    }
};

用DFS是更正确的解法：

class Solution {
public:
    int row;
    int col;
    vector<vector<bool>> visited;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    bool wordPuzzle(vector<vector<char>>& grid, string target) {
        if(grid.empty() || grid[0].empty()) return false; 
        row = grid.size();
        col = grid[0].size();

        visited.resize(row);
        for(auto& perrow: visited){
            perrow.resize(col, false);
        }

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(dfs(grid, i, j, target, 0)){
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& grid, int i, int j, string& s, int k){
        // 两个判断顺序不能换
        if(s[k] != grid[i][j]){
            return false;
        }
        if(k == s.size() - 1) return true;
        

        // 进到这里 说明s[k] == grid[i][j] 并且还没完全全字匹配
        visited[i][j] = true;
        bool result = false;

        for(int l = 0; l < 4; l++){
            int curx = dx[l] + i;
            int cury = dy[l] + j;
            if(curx < 0 || curx >= row || cury < 0 || cury >=col){
                continue;
            }
            if(!visited[curx][cury]){
                // dfs下一层
                if(dfs(grid, curx, cury, s, k+1)){
                    result = true;
                    break;
                }
            }
        }
        //最后记得还原现场
        visited[i][j] = false;
        return result;
    }
};