JZ12矩阵中的路径_JZ13机器人的运动范围

JZ12矩阵中的路径

矩阵中的路径


import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public int[][] nextP = {{1,0},{-1,0},{0,1},{0,-1}};
    public boolean dfs(char[][] matrix,int x,int y,String word,int pos){
        //广度优先遍历!
        if(pos==word.length()-1){
            return true;
        }
        for(int i=0;i<nextP.length;i++){
                int curx = x+nextP[i][0];
                int cury = y+nextP[i][1];
                if(curx<matrix.length&&curx>=0&&cury<matrix[0].length&&cury>=0){
                    if(word.charAt(pos+1)==matrix[curx][cury]){
                        //相等!
                        //标记走过!
                        char tmp = matrix[curx][cury];
                        matrix[curx][cury]='0';
                         if(dfs(matrix,curx,cury,word,pos+1)){
                             //满足
                             return true;
                         }else{
                             //不满足
                            matrix[curx][cury]=tmp;
                         }
                        //处理下一个位置!
                    }
            }
        }
        return false;
    }
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        for(int i = 0;i< matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(matrix[i][j]==word.charAt(0)){
                    //找到入口!
                    if(dfs(matrix,i,j,word,0)){//广度优先!
                        //满足
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

JZ13机器人的运动范围

机器人的运动轨迹



import java.util.*;
class pare{
    int x;
    int y;
    public pare(int x,int y){
        this.x = x;
        this.y = y;
    }
}
public class Solution {
    public int help(int x){
        //求位数之和!
        int count = 0;
        while(x!=0){
            count+=x%10;
            x/=10;
        }
        return count;
    }
    public int movingCount(int threshold, int rows, int cols) {
        //dfs广度优先遍历!
        //初始化队列!
        Queue<pare> q = new LinkedList<>();
        q.offer(new pare(0,0));
        int[][] next = {{1,0},{-1,0},{0,1},{0,-1}};
        int count = 0;
        boolean[][] table = new boolean[rows][cols];
        table[0][0] = true;
        while(!q.isEmpty()){
            int size = q.size();
               pare cur = q.poll();//出队!
              //计数 
              count++;
            while(size-->0){
                for(int i=0;i<next.length;i++){
                   int  nextx = next[i][0] + cur.x;
                   int  nexty = next[i][1] + cur.y;
                    int sum = help(nextx) + help(nexty);
                    if(nextx<rows&&nextx>=0&&nexty<cols&&nexty>=0
                       &&sum<=threshold&&!table[nextx][nexty]){
                        //入队!
                        q.offer(new pare(nextx,nexty));
                        //标记走过!
                        table[nextx][nexty] =true;
                    }
                }
            }
        }
        return count;
    }
}

public class Solution {
    //记录遍历的四个方向
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    //记录答案
    int res = 0;
    //计算一个数字的每个数之和
    int cal(int n){
        int sum = 0;
        //连除法算出每一位
        while(n != 0){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }
    //深度优先搜索dfs
    void dfs(int i, int j, int rows, int cols, int threshold, boolean[][] vis){
        //越界或者已经访问过
        if(i < 0 || i >= rows || j < 0 || j >= cols || vis[i][j] == true)
            return;
        //行列和数字相加大于threshold，不可取
        if(cal(i) + cal(j) > threshold)
            return;
        res += 1;
        //标记经过的位置
        vis[i][j] = true;
        //上下左右四个方向搜索
        for(int k = 0; k < 4; k++)
            dfs(i + dir[k][0], j + dir[k][1], rows, cols, threshold, vis);
    }
    public int movingCount(int threshold, int rows, int cols) {
        //判断特殊情况
        if(threshold <= 0)
            return 1;
        //标记某个格子没有被访问过
        boolean[][] vis = new boolean[rows][cols];
        dfs(0, 0, rows, cols, threshold, vis);
        return res;
    }
}