LCR130

问题描述

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

原问题有些描述不清，这里其实是问，可以整理的格子连成一片一片的，最大的那一片有多少格？

题解

DFS、BFS遍历即可解，最大的那一块一定包含(0,0)，所以从(0,0)开始向右向下DFS。

class Solution {
  boolean[][] visited;
  int m,n,cnt;
  public int wardrobeFinishing(int m, int n, int cnt) {
     this.m=m;this.n=n;this.cnt=cnt;
     this.visited = new boolean[m][n];
     return DFS(0,0);
  }
  public int digit(int i){
     int res = 0;
     while(i>0){
       res+=i%10;
       i/=10;
     }
     return res;
  }
  
  public int DFS(int i,int j){
     if(i>=m||j>=n||visited[i][j]||digit(i)+digit(j)>cnt) return 0;
     visited[i][j]=true;
     return DFS(i+1,j)+DFS(i,j+1)+1;
  }
}