剑指Offer-第14天 搜索与回溯算法（中等）

第一题

题目链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/

个人题解：

  1. 从 \((0,0)\) 点开始深搜
  2. 记录一个长度值 \(u\)，如果发现 \(board[x][y]!=u\) 直接退出
  3. 如果 \(u==words.size()-1\)，则找到。
  4. 否则按照深搜的板子做就可以了

代码：

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

    bool dfs(vector>& board,string word,int u,int x,int y){
        if(board[x][y]!=word[u]) return false;//不一样就错了
        if(u+1==word.size()) return true;// 找到了
        
        char tmp=board[x][y];
        board[x][y]='.';
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && a=0 && b>& board, string word) {
        for(int i=0;i

运行截图：

第二题

题目链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

个人题解：宽搜即可，套用板子

代码：

#define x first
#define y second
typedef pair PII;

class Solution {
public:
    int dx[2]={0,1},dy[2]={1,0};

    int get(int x){
        int res=0;
        while(x){
            res+=x%10;
            x/=10;
        }
        return res;
    }

    int movingCount(int m, int n, int k) {
        if(!k) return 1;
        
        int cnt=0;

        vector> st(m,vector(n,0));
        st[0][0]=1;
        queue q;
        q.push({0,0});

        while(!q.empty()){
            auto t=q.front(); q.pop();
            cnt++;
            for(int i=0;i<2;i++){
                int a=dx[i]+t.x,b=dy[i]+t.y;
                if(a<0 || a>=m || b<0 || b>=n || st[a][b] || get(a)+get(b)>k) continue;
                q.push({a,b});
                st[a][b]=1;
            }
        }
        return cnt;
    }
};

运行截图：

复刷剑指Offer

相关

标签