深度优先和广度优先的搜索

步骤：

  1. 模式识别：更适合广度优先还是深度优先
  2. 确定当前的状态，根据状态进行递归操作
  3. 确定递归的模式（可使用队列进行辅助）
  4. 查看是否需要记录状态

Example

机器人走路

  1. 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
  1. class Solution {
  2.     int result = 0;
  3.     boolean[][] map;
  5.     public int movingCount(int m, int n, int k) {
  6.         map = new boolean[m][n];
  7.         //1.列出m,n的矩阵
  8.         //2.写出计算函数
  9.         //3.确定当前状态
  10.         //4.进行递归，记录状态
  11.         //结果进行计数
  12.         //边界和极值0
  14.         //递归
  15.         f(0,0,m,n,k);
  16.         return result;
  17.     }
  19.     public void f(int x, int y ,int m ,int n, int k){
  20.         if(!checkLimit(x,y,m,n)) return;
  21.         if(!checkSum(x,y,k)) return;
  22.         result += 1;
  23.         map[y][x] = true;
  25.         f(x+1,y,m,n,k);
  26.         f(x,y+1,m,n,k);
  27.         f(x-1,y,m,n,k);
  28.         f(x,y-1,m,n,k);
  29.     }
  31.     public boolean checkLimit(int x, int y, int m,int n){
  32.         if(x<0 || x >= n) return false;
  33.         if(y<0 || y>= m) return false;
  34.         if(map[y][x]) return false;
  36.         return true;
  37.     }
  39.     public boolean checkSum(int x ,int y, int k){
  40.         int count = 0;
  41.         while(x / 10 > 0){
  42.             count += x % 10;
  43.             x = x / 10;
  44.         }
  45.         count += x;
  46.         while(y / 10 > 0){
  47.             count += y%10;
  48.             y = y / 10;
  49.         }
  50.         count += y;
  51.         if(k < count) return false;
  53.         return true;
  54.     }
  55. }