算法手记4

一.单词搜索

牛客网题目链接(点击即可跳转):NC242 单词搜索

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下: 对二维数组的每一个位置都dfs一下,如果找到完整的单词就返回true,如果全部找完都没找到就返回false. 主函数的逻辑是bfs完每一个二维数组里符合第一个字母的位置,如果找到就返回找到了,没找到就找下一个符合的,遍历完还没找到就返回false. bfs的逻辑是,从当前位置开始搜索四个方位有没有符合下一个字母的,如果有,进去递归下一个字母,如果没有,返回当前路径失败,退回寻找下一路径. 一定要记得字母不可以重复使用,所以每到一个位置就要锁一个位置!如果该位置被弃用则要释放锁.

解题代码:

本题解题代码如下:

class Solution 
{
public:
    int vis[101][101]={0};//标记这个位置是否被用过
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    
    bool exist(vector<string>& board, string word) 
    {
        //遍历二维数组,找到第一个字符,然后广度优先搜索
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {

                if(board[i][j] == word[0]) 
                    if(bfs(board,word,0,i,j)==true) return true;//有一次成了就返回true
            }
        }
        return false;//没一次成功,返回false
    }

    bool bfs(vector<string>& board,string& word,int pos,int x,int y)
    {
        //如果递归到单词的最后一个字母,结束返回true
        if(pos == word.size()-1)    return true;
        //进入这个位置就把这个位置锁住
        vis[x][y] = 1;

        //如果递归的是中间字符,继续搜索4个方位有没有符合下一个的,如果有,继续递归搜
        for(int i=0; i<4; i++)
        {
            int a = x+dx[i],b=y+dy[i];
            if(a>=0 && a<board.size() && b>=0 && b<board[0].size() && !vis[a][b] && board[a][b]==word[pos+1])
                if(bfs(board,word,pos+1,a,b))return true;
        }

        //如果四个位置找完没有符合下一个字符的,那么释放本位置的锁,返回false
        vis[x][y]=0;
        return false;
    }
};

结语

说点啥好呢...牵扯二维的算法就有点难了,但其实边界照常处理就行,一维的循环在n内,二维的两层循环在x,y内,不要去想的那么麻烦,二维其实就是机械化的处理一批一维数据罢了,还有不要抗拒递归,你想象它就是二叉的一个分支,你只要考虑你这个结点的前和后就行了,不要去管别的路径情况啥样,每个结点和分支都管好自己,最后就可以把准确的结果送达顶端.