矩阵中的路径

关键词：深度优先算法dfs

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,”b“,”c”,”e”],

[“s”,”f“,”c“,”s”],

[“a”,”d”,”e“,”e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

1 2	`输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true`

示例2：

1 2	`输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false`

思路

思路一：

在board中找到一个位置，使得board[i][j]== word[0]，可以作为搜索的入口；

由于不能重复进入，因此需要定义一个visit数组，保证每个格子只进入一次；

找到一个可行解即返回true。若该次搜索返回false，那么进行寻找下一个可行的入口，进入下一次搜索；

直到遍历完整个board，仍没有搜索到目标路径，返回false。

代码

思路一：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

//四个方向
vector<vector<int> > dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool checkpath(vector<vector<char> >& board, vector<vector<int> >&vis, int x, int y, string& word, int idx)
{
    vis[x][y] = 1;//将当前位置设为已访问
    if(idx == word.size()) return true;//已经遍历完word
    for(auto xy : dir){//四个方向
        int nextx = x + xy[0], nexty = y + xy[1];
        if(nextx < 0 || nextx >= board.size() || nexty < 0 || nexty >= board[0].size()
           || vis[nextx][nexty]
           || board[nextx][nexty] != word[idx])//判断边界条件、是否访问和是否为目的字符
            continue;
        else{//进行下一次遍历
            if(checkpath(board, vis, nextx, nexty, word, idx + 1)) return true;
        }
    }
    vis[x][y] = 0;//记得将当前位置复原
    return false;
}

bool exist(vector<vector<char> >& board, string word)
{
    //判断输入是否合理
    int row = board.size();
    if(row < 1) return false;
    int col = board[0].size();
    if(col < 1) return false;
    vector<vector<int>>vis(row, vector<int>(col, 0));//与原矩阵大小一样的零矩阵，用于表示当前位置是否已经访问过
    for(int x = 0; x < row; x++){
        for(int y = 0; y < col; y++){
            if(board[x][y] == word[0]){//入口
                bool isexist = checkpath(board, vis, x, y, word, 1);
                if(isexist) return true;
            }
        }
    }
    return false;
}


int main()
{
    vector<vector<char> > board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};//注意{}和''
    string word = "ADECSE";
    bool a = exist(board, word);
    cout << a << endl;
    return 0;
}

知识点

深度优先算法dfs
方向数组的定义
auto的使用