class Solution {
public:
int m;
int n;
int k;
int wardrobeFinishing(int m, int n, int cnt) {
this->m = m;
this->n = n;
this->k = cnt;
vector<vector<bool>> visited(m,vector<bool>(n,false));
return dfs(0,0,visited);
}
int dfs(int i,int j, vector<vector<bool>>& visited)
{
if(i<0 || j<0 || i>=m || j>=n || visited[i][j] || (sum(i)+sum(j))>k)
{
return 0;
}
visited[i][j] = true;
return 1+dfs(i,j+1,visited) + dfs(i+1,j,visited);
}
int sum(int x)
{
int res = 0;
while(x != 0)
{
res += x%10;
x /= 10;
}
return res;
}
};
class Solution {
int n;//grid 行数
int m; // 列数
int cnt;
boolean[][] visited;
public int wardrobeFinishing(int m, int n, int cnt) {
this.n=n;
this.m=m;
this.cnt=cnt;
visited = new boolean[n][m];
return dfs(0,0,cnt);
}
int dfs(int i,int j,int cnt){
if(i<0 || i>=n || j<0 || j>=m ||visited[i][j]==true || digit(i)+digit(j)>cnt){
return 0;
}
visited[i][j]=true;
return 1+dfs(i+1,j,cnt)+dfs(i,j+1,cnt);//这个方向也可以访问，+1
}
int digit(int n){
int sum=0;
while(n!=0){
sum+=(n%10);
n=n/10;
}
return sum;
}
}
class Solution {
public:
int wardrobeFinishing(int m, int n, int cnt) {
if(!cnt) return 1;
vector<vector<bool>> vis(m, vector<bool>(n, false));
dfs(0, 0, m, n, cnt, vis);
return res;
}
private:
int getSum(int x) {
int sum = 0;
for(; x; x /= 10) sum += x % 10;
return sum;
}
void dfs(int i, int j, int m, int n, int cnt, vector<vector<bool>>& vis) {
if (i < 0 || j < 0 || i >= m || j >= n || vis[i][j] || getSum(i) + getSum(j) > cnt) return;
res++;
vis[i][j] = true;
dfs(i + 1, j, m, n, cnt, vis), dfs(i, j + 1, m, n, cnt, vis);
}
private:
int res;
};
/*
0 1 2 3 4 5 6
1
2
3
*/
class Solution {
int m;
int n;
int k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m;
this.n = n;
this.k = k;
visited = new boolean[m][n];
return dfs(0, 0);
}
int dfs(int i, int j){
// 是否在方格之内或者是否访问过或者是否是障碍物
if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)){
return 0;
}
visited[i][j] = true;
return 1 + dfs(i + 1, j) + dfs(i, j + 1);
}
int sum(int x){
int res = 0;
while(x != 0){
res = res + x % 10;
x = x / 10;
}
return res;
}
}
class Solution {
public:
int wardrobeFinishing(int m, int n, int cnt) {
this->m = m;
this->n = n;
this->k = cnt;
this->visited.resize(m, vector<bool>(n, false));
return dfs(0, 0);
}
int dfs(int i, int j){
if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j] == true || k < sum(i) + sum(j))
return 0;
visited[i][j] = true;
return 1 + dfs(i + 1, j) + dfs(i, j + 1);
}
int sum(int x){
int res = 0;
while(x != 0){
res += x % 10;
x /= 10;
}
return res;
}
private:
int n;
int m;
int k;
vector<vector<bool>> visited;
};
“`c++
class Solution {
public:
int wardrobeFinishing(int m, int n, int cnt) {
vector> visited(m, vector(n, false));
return dfs(visited, 0, 0, m, n, cnt, 0, 0);
}
int dfs(vector> &visited, int row, int col, int m, int n, int cnt, int valr, int valc) {
if (row >= m || col >= n || valr+valc > cnt || visited[row][col]==1) return 0;
visited[row][col] = true;
return 1 + dfs(visited, row+1, col, m, n, cnt, (row+1)%10==0?(valr-8):(valr+1), valc) + dfs(visited, row, col+1, m, n, cnt, valr, (col+1)%10==0?(valc-8):(valc+1));
}
};
“`
class Solution {
int m,n,cnt;
boolean[][] visited;
public int wardrobeFinishing(int m, int n, int cnt) {
this.m = m; this.n = n; this.cnt = cnt;
visited = new boolean[m][n];
return dfs(0, 0);
}
//当前元素在矩阵中的行列索引 i 和 j
int dfs(int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || sumOfDigits(i) + sumOfDigits(j) > cnt) {
return 0;
}
visited[i][j] = true;
return 1 + dfs(i+1, j) + dfs(i, j+1);
}
int sumOfDigits(int x){
int sum = 0;
while(x != 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
}
class Solution {
Boolean[][] hasVisited;
int count = 0;
public int wardrobeFinishing(int m, int n, int cnt) {
hasVisited = new Boolean[m][n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
hasVisited[i][j] = false;
visit(m,n,cnt,0,0);
return count;
}
private void visit(int m, int n, int cnt, int x, int y){
if(x >= m || y >= n || digit(x) + digit(y) > cnt ||hasVisited[x][y] == true)
return;
hasVisited[x][y] = true;
count++;
visit(m,n,cnt,x+1,y);
visit(m,n,cnt,x,y+1);
}
private int digit(int x){
int digit = 0;
while(x!=0){
digit += x % 10;
x /= 10;
}
return digit;
}
class Solution {
int res = 0;
public int wardrobeFinishing(int m, int n, int cnt) {
boolean[][] visited = new boolean[m][n];
backtrace(m,n,0,0,cnt,visited);
return res;
}
public void backtrace(int m,int n,int i,int j,int cnt,boolean[][] visited){
if(getSum(i)+getSum(j)>cnt||visited[i][j]){
return;
}
res++;
visited[i][j] = true;
int[][] directions = new int[][]{{0,1},{1,0}};
for(int[] direction:directions){
int newi = i+direction[0];
int newj = j+direction[1];
if(newi<m&&newi>=0&&newj<n&&newj>=0){
backtrace(m,n,newi,newj,cnt,visited);
}
}
}
public int getSum(int x){
int sum = 0;
while(x!=0){
sum = sum + x%10;
x/=10;
}
return sum;
}
}
思路：回溯（深度优先搜索），定义全局变量res用来返回结果，如果当前位置没被访问过且digit(i)+digit(j)<=cnt的话就res++且访问下一个节点。
class Solution {
public:
int wardrobeFinishing(int m, int n, int cnt) {
vector<vector> flag(m, vector(n, 0));
return dfs(0, 0, cnt, flag);
}
private:
int digit(int x) {
return x / 10 + x % 10;
}
int dfs(int x, int y, int cnt, vector<vector>& flag) {
if (x >= flag.size() || y >= flag[0].size() || digit(x) + digit(y) > cnt || flag[x][y])
return 0;
flag[x][y] = 1;
int res = 1 + dfs(x + 1, y, cnt, flag) + dfs(x, y + 1, cnt, flag);
return res;
}
};时间空间复杂度均为O(MN)
shuaidi
共以下 10 个回答
时间复杂度O(mn)，空间复杂度O(mn)
时间复杂度：O(mn)
空间复杂度：O(mn)
打卡
时间复杂度: O(m * n)
思路：dfs
“`c++> visited(m, vector(n, false));> &visited, int row, int col, int m, int n, int cnt, int valr, int valc) {
class Solution {
public:
int wardrobeFinishing(int m, int n, int cnt) {
vector
return dfs(visited, 0, 0, m, n, cnt, 0, 0);
}
int dfs(vector
if (row >= m || col >= n || valr+valc > cnt || visited[row][col]==1) return 0;
visited[row][col] = true;
return 1 + dfs(visited, row+1, col, m, n, cnt, (row+1)%10==0?(valr-8):(valr+1), valc) + dfs(visited, row, col+1, m, n, cnt, valr, (col+1)%10==0?(valc-8):(valc+1));
}
};
“`
时间复杂度$O(mn)$，空间复杂度$O(mn)$
class Solution {
Boolean[][] hasVisited;
int count = 0;
public int wardrobeFinishing(int m, int n, int cnt) {
hasVisited = new Boolean[m][n];
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
hasVisited[i][j] = false;
visit(m,n,cnt,0,0);
return count;
}
//时间复杂度Onm
空间复杂度Onm
class Solution {> flag(m, vector (n, 0)); >& flag) {
public:
int wardrobeFinishing(int m, int n, int cnt) {
vector<vector
return dfs(0, 0, cnt, flag);
}
private:
int digit(int x) {
return x / 10 + x % 10;
}
int dfs(int x, int y, int cnt, vector<vector
if (x >= flag.size() || y >= flag[0].size() || digit(x) + digit(y) > cnt || flag[x][y])
return 0;
flag[x][y] = 1;
int res = 1 + dfs(x + 1, y, cnt, flag) + dfs(x, y + 1, cnt, flag);
return res;
}
};时间空间复杂度均为O(MN)