//思路：dfs,搜索四个方向，vis记录该方格是否被搜索过，
// 预判方格是否合法，合法就从该方格接着搜索  

const int MAXN=100;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};    //四个方向	
int vis[MAXN][MAXN]={0};    //记录数组
int sum;    //记录结果

class Solution {
public:
    void dfs(int x,int y,int k,int m,int n)
    {
        vis[x][y]=1;
        for(int i=0;i<=3;++i)
        {
            int newx=x+dx[i],newy=y+dy[i];
            //预判方格是否合法，合法就从该方格接着搜索 
       if(vis[newx][newy]==0&&newx>=0&&newx<m&&newy>=0&&newy<n&&(newx%10+newx/10+newy%10+newy/10<=k))
            {
                ++sum;
                dfs(newx,newy,k,m,n);
            }
        }
    }
    int movingCount(int k, int rows, int cols)
    {
        if(k<0)
            return 0;
        memset(vis,0,sizeof(vis));
        sum=1;
        dfs(0,0,k,rows,cols);
        return sum;
        
    }
};

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        bool* flag=new bool[rows*cols];
        for(int i=0;i<rows*cols;i++)
            flag[i]=false;
        int count=moving(threshold,rows,cols,0,0,flag);//从（0,0）坐标开始访问;
        delete[] flag;
        return count;
    }
    //计算最大移动位置
    int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
    {
        int count=0;
        if(check(threshold,rows,cols,i,j,flag))
        {
            flag[i*cols+j]=true;
            //标记访问过，这个标志flag不需要回溯，因为只要被访问过即可。
           //因为如果能访问，访问过会加1.不能访问，也会标记下访问过。
            count=1+moving(threshold,rows,cols,i-1,j,flag)
                   +moving(threshold,rows,cols,i,j-1,flag)
                   +moving(threshold,rows,cols,i+1,j,flag)
                   +moving(threshold,rows,cols,i,j+1,flag);
        }
        return count;
    }
    //检查当前位置是否可以访问
    bool check(int threshold,int rows,int cols,int i,int j,bool* flag)
    {
        if(i>=0 && i<rows && j>=0 && j<cols 
            && getSum(i)+getSum(j)<=threshold 
            && flag[i*cols+j]==false)
           return true;
        return false;
    }
    //计算位置的数值
    int getSum(int number)
    {
        int sum=0;
        while(number>0)
        {
            sum+=number%10;
            number/=10;
        }
        return sum;
    }
};

//java简单易懂版
public class Solution {
    int count=0;
    public int movingCount(int threshold, int rows, int cols)
    {
        boolean[] pass = new boolean[rows*cols];
        movingCount(threshold,0,0,rows,cols,pass);
        return count;
    }
    public void movingCount(int threshold, int i, int j,int rows, int cols,boolean[] pass){
        int index = i*cols+j;
        if(i<0||j<0||i>=rows||j>=cols||pass[index]==true)
            return ;
        if(helper(i,j)<=threshold){
            count++;
            pass[index]=true;
        }else{
            pass[index]=false;
            return;
        }
        movingCount(threshold, i-1, j,rows,  cols,pass);
        movingCount(threshold, i+1, j,rows,  cols,pass);
        movingCount(threshold, i, j-1,rows,  cols,pass);
        movingCount(threshold, i, j+1,rows,  cols,pass);
    }
    public int helper(int i,int j){
        int sum = 0;
        do{
            sum += i%10;
        }while((i = i/10) > 0);
        
        do{
            sum += j%10;
        }while((j = j/10) > 0);
        return sum;
    }
}

class Solution {
    bool canreach(int threshold, int x, int y) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        while (y > 0) {
            sum += y % 10;
            y /= 10;
        }
        return sum <= threshold;
    }
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>> grid(rows);
        for (auto& row : grid) {
            row.resize(cols, false);
        }
        queue<pair<int, int>> que;
        if (canreach(threshold, 0, 0)) {
            que.push(make_pair(0, 0));
            grid[0][0] = true;
        }
        int cnt = 0;
        while (!que.empty()) {
            ++cnt;
            int x, y;
            tie(x, y) = que.front();
            que.pop();
            if (x + 1 < rows && !grid[x + 1][y] && canreach(threshold, x + 1, y)) {
                grid[x + 1][y] = true;
                que.push(make_pair(x + 1, y));
            }
            if (y + 1 < cols && !grid[x][y + 1] && canreach(threshold, x, y + 1)) {
                grid[x][y + 1] = true;
                que.push(make_pair(x, y + 1));
            }
        }
        return cnt;
    }
};

这道是典型的DFS || BFS 题

public class Solution {

    /**算法本质：
    * DFS||BFS 寻找连通分量
    * 
     * 题目分析：
     * 机器人在一个矩阵上的m*n个格子上移动，可进入的格子的集合可抽象为以下点集：
     * { (row, col) | (i%10+i/10+j%10+j/10) <= threshold }。且路径节点可重复，无步数限制。
     * 问：机器人能到达多少个格子？
     * 
     * 题目抽象：
     * 倘若我们把矩阵的每一个“格子”抽象成一个“结点”，把“格子相邻”抽象为“结点连通”（结点之间存在无向边），
     * 把“无法进入的格子”抽象成“与所有普通结点都不连通（不存在无向边）的孤点”，则整个问题可以抽象为：
     * 从某个结点出发，寻找无向图的连通分量的节点个数。很显然，可以使用DFS或者BFS进行实现
     * 
     * 算法实现：
     * 这里选择DFS进行实现。
     * 设置两个辅助boolean矩阵：visited与isWall。前者是DFS中的典型辅助矩阵，记录每个节点是否已访问过。
     * 后者用来表示每个节点是否是不能进入的“孤点”。
     * 设置静态变量nodeCnt，用于在DFS的过程中记录访问过的结点数
     * DFS递归函数的出口条件设置为：   
     * (outOfBoundary(rows, cols, row, col) || visited[row][col] || isWall[row][col] )
     * 即：“若超过边界（到矩阵之外）”或“访问过”或“是无法进入的结点” 则 return
     * 然后进行DFS。
     * */

    int nodeCnt = 0;
    boolean[][] visited;
    boolean[][] isWall;
    int threshold;
    int rows;
    int cols;

    public int movingCount(int threshold, int rows, int cols){
        if (threshold<0 || rows<=0 || cols<=0) //robust
            return 0;//牛客示例是0

        //init
        this.nodeCnt = 0;
        this.threshold = threshold;
        this.rows = rows;
        this.cols = cols;
        this.visited = new boolean[rows][cols];
        this.isWall = new boolean[rows][cols];
        for (int i=0;i<rows;i++){
            for (int j=0;j<cols;j++){
                this.visited[i][j]=false;
                if ( (i%10+i/10+j%10+j/10) > threshold )
                    this.isWall[i][j]=true;
                else
                    this.isWall[i][j]=false;
            }
        }

        //body
        DFS(0,0);
        return this.nodeCnt;
    }

    public void DFS(int row, int col){
        if (   outOfBoundary(rows, cols, row, col) 
            || visited[row][col] 
            || isWall[row][col] )
            return;

        //visit
        visited[row][col]=true;
        nodeCnt++;

        //DFS
        DFS(row+1, col);
        DFS(row-1, col);
        DFS(row, col+1);
        DFS(row, col-1);
    }

    public boolean outOfBoundary(int rows, int cols, int row, int col){
        return ( row<0 || row>=rows || col<0 || col>=cols );
    }

}

python solution:

class Solution:
    def movingCount(self, threshold, rows, cols):
        self.row, self.col = rows, cols
        self.dict = set()
        self.search(threshold, 0, 0)
        return len(self.dict)

    def judge(self, threshold, i, j):
        return sum(map(int, list(str(i)))) + sum(map(int, list(str(j)))) <= threshold

    def search(self, threshold, i, j):
        if not self.judge(threshold, i, j) or (i, j) in self.dict:
            return
        self.dict.add((i, j))
        if i != self.row - 1:
            self.search(threshold, i + 1, j)
        if j != self.col - 1:
            self.search(threshold, i, j + 1)

要注意去重:(i,j) in self.dict

如果不加这一句，时间复杂度不会满足。

public class Solution {
 
    public int movingCount(int threshold, int rows, int cols) {
       int[][] flag = new int[rows][cols];
       return moving(threshold, rows, cols, flag, 0, 0);
    }
    
    public int moving(int threshold, int rows, int cols, int[][] flag, int i, int j){
        if(threshold <= 0 || i >= rows || i< 0 || j >= cols || j < 0 || (flag[i][j] == 1) || (sum(i) + sum(j) > threshold)){
            return 0;
        }
        flag[i][j] = 1;
        return moving(threshold, rows, cols, flag, i - 1, j)
            +moving(threshold, rows, cols, flag, i + 1, j)
            +moving(threshold, rows, cols, flag, i, j - 1)
            +moving(threshold, rows, cols, flag, i, j + 1)
            + 1;    
    }
    
    public int sum(int i ){
        if(i == 0){return i ;}
        int sum = 0;
        while(i != 0){
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }

}

利用队列宽度优先搜索
代码有点长但是很清晰

class Solution {
public:

    bool if_ok(int x, int y, int th){
        int sum = 0;
        string sx = to_string(x);
        string sy = to_string(y);
        for(int i = 0; i < sx.length();i++) sum += sx[i]-'0';
        for(int i = 0; i < sy.length();i++) sum += sy[i]-'0';
        return sum <= th;
    }


    int movingCount(int threshold, int rows, int cols){
        if(threshold <= 0) return 0;
        int stepx[4] = {1, -1, 0, 0};
        int stepy[4] = {0, 0, 1, -1};
        vector<vector<int> > dp(rows, vector<int>(cols, 0));
        queue<int> qx; queue<int> qy;
        qx.push(0); qy.push(0); dp[0][0] = 1;
        int ans = 0;
        while(!qx.empty()){
            ans++;
            int x = qx.front(); qx.pop();
            int y = qy.front(); qy.pop();
            for(int i = 0; i < 4; i++){
                if(x+stepx[i]<rows && x+stepx[i]>=0 &&
                   y+stepy[i]<cols && y+stepy[i]>=0 &&
                   if_ok(x+stepx[i],y+stepy[i],threshold) &&
                   dp[x+stepx[i]][y+stepy[i]] == 0){
                        qx.push(x+stepx[i]);
                        qy.push(y+stepy[i]);
                        dp[x+stepx[i]][y+stepy[i]] = 1;
                }
            }
        }
        return ans;
    }
};

python solution:

class Solution:
    def getDigitSum(self,number):
        return sum(map(int,list(str(number))))
    def check(self,threshold,rows,cols,row,col,visited):
        if row>=0 and row<rows and col>=0 and col<cols and self.getDigitSum(row)+self.getDigitSum(col)<=threshold and not (row,col) in visited:
            return True
        return False
    def movingCountCore(self,threshold, rows, cols, row, col, visited):
        count=0
        if self.check(threshold,rows,cols,row,col,visited):
            visited.add((row,col))
            count=1+self.movingCountCore(threshold,rows,cols,row-1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col-1,visited)+self.movingCountCore(threshold,rows,cols,row+1,col,visited)+self.movingCountCore(threshold,rows,cols,row,col+1,visited)
        return count
    def movingCount(self,threshold, rows, cols):
        # write code here
        if threshold<0 or rows<=0 or cols<=0:
            return 0
        visited=set()
        count=self.movingCountCore(threshold,rows,cols,0,0,visited)
        return count

//非递归，利用栈实现
class Solution {
public:
    int Count(int row, int col){
        int count=0;
        while(row||col){
            count+=row%10+col%10;
            row/=10;
            col/=10;
        }
        return count;
    }
    int movingCount(int threshold, int rows, int cols){
        if((rows<1&&cols<1)||threshold<0)
            return 0;
        int R=1;
        bool* visited=new bool[rows*cols];
        memset(visited,0,rows*cols);
        visited[0]=true;
        stack<int> S;
        S.push(0);
        int p[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        while(!S.empty()){
            int i=S.top()/cols,j=S.top()%cols;
            S.pop();
            for(int k=0;k<4;k++){
                int row=i+p[k][0],col=j+p[k][1];
                if(row>=0&&row<rows&&col>=0&&col<cols&&!visited[row*cols+col]&&Count(row,col)<=threshold){
                    S.push(row*cols+col);
                    visited[row*cols+col]=true;
                    R++;
				}
            }  
        }
        return R;
    }
};

//回溯法。仔细审题。。。
class Solution {
public:
	int movingCount(int threshold, int rows, int cols) {
		int res = 0;
		bool* flag = new bool[rows*cols];
		memset(flag, 0, rows*cols);
		dfs(threshold, rows, cols, flag, 0, 0, res);
		return res;
	}
	void dfs(int threshold, int rows, int cols, bool* flag, int i, int j, int &res) {
		if (i<0 || i >= rows || j<0 || j >= cols)
			return;
		if (*(flag + i*cols + j) == 1)
			return;
		if (check(i,j,threshold)){
			res++;
			*(flag + i*cols + j) = 1;
			dfs(threshold, rows, cols, flag, i, j - 1, res);//左
			dfs(threshold, rows, cols, flag, i, j + 1, res);//右
			dfs(threshold, rows, cols, flag, i - 1, j, res);//上
			dfs(threshold, rows, cols, flag, i + 1, j, res);//下
		}
	}
    bool check(int ii,int jj,int threshold){
        int sum = 0;
        while (ii != 0) {
			sum += ii % 10;
			ii = ii / 10;
		}
		while (jj != 0) {
			sum += jj % 10;
			jj = jj / 10;
		}
        return sum<=threshold;
    }
};

class Solution {
public:
  // BFS
  int movingCount(int threshold, int rows, int cols) {
    using P = pair<int, int>;
    vector<vector<int>> grid(rows, vector<int>(cols, 0));
    
    deque<P> q;
    q.emplace_back(0, 0);
    grid[0][0] = 1;
    
    const vector<int> dirs { 0, -1, 0, 1, 0 };
    
    int ans = 0;
    while (not q.empty()) {
      const auto [x, y] = q.front(); q.pop_front();
      ++ans;
      for (int i = 0; i < 4; ++i) {
        const int nx = x + dirs[i], ny = y + dirs[i + 1];
        if (not available(grid, rows, cols, nx, ny, threshold))
          continue;
        q.emplace_back(nx, ny);
        grid[ny][nx] = 1;
      }
    }
  
    return ans;
  }
  
  // DFS
  int movingCountII(int threshold, int rows, int cols) {
    vector<vector<int>> grid(rows, vector<int>(cols, 0));
    
    function<int(int, int)> dfs = [&](int x, int y) -> int {
      if (not available(grid, rows, cols, x, y, threshold))
        return 0;
      
      grid[y][x] = 1; // mark as seen
      
      int cnt = 1;
      cnt += dfs(x - 1, y);
      cnt += dfs(x + 1, y);
      cnt += dfs(x, y - 1);
      cnt += dfs(x, y + 1);
      return cnt;
    };
    
    return dfs(0, 0);
  }
  
private:
  bool available(vector<vector<int>>& grid, int rows, int cols, int x, int y, int threshold) {
    if (x < 0 || y < 0 || x == cols || y == rows || grid[y][x])
      return false;

    int s = 0;
    while (x) {
      s += x % 10;
      x /= 10;
    }
    while (y) {
      s += y % 10;
      y /= 10;
    }
    
    return s <= threshold;
  } 
};

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # 计算每一位之和
        def getsum(num):
            sum = 0
            while num>0:
                sum += num%10
                num = num//10
            return sum
        path = []
        def back(start):
            if start in path or getsum(start[0]) + getsum(start[1])> threshold:
                return None
            if start[0]>=rows or start[1]>=cols:
                return None
            path.append(start)       # 从0，0开始向右向下遍历，减少走回头路的次数             
            back([start[0]+1,start[1]])
            back([start[0],start[1]+1])
        back([0,0])
        return len(path) 
           

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<int> isVisit(rows*cols, 0);
        return helper(threshold, rows, cols, 0, 0, isVisit);
    }
private:
    int helper(int threshold, int rows, int cols, int row, int col, vector<int>& isVisit)
    {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||digitnum(row) + digitnum(col) > threshold || isVisit[row*cols+col] == 1)
            return 0;
        isVisit[row*cols+col] = 1;
        return 1 + helper(threshold, rows,cols, row-1, col,isVisit) +
            helper(threshold, rows,cols, row+1, col,isVisit) +
            helper(threshold, rows,cols, row, col-1,isVisit) +
            helper(threshold, rows,cols, row, col+1,isVisit);
        
    }
    int digitnum(int num)
    {
        int cnt = 0;
        while(num)
        {
            cnt += num % 10;
            num /= 10;
        }
        return cnt;
    }
};

思路

• 这么多DFS的 我分享一个BFS的
• 用队列记录每一个合法的点（BFS一般都用队列）
• 建立二维数组标记走过的点，同时注意入队的时候就标记已经走过，否则下次还会入队
• 注意threshold小于0的情况

import java.util.*;
class Point{
    int x;
    int y;
    public Point(int a,int b){
        x = a;
        y = b;
    }
}
public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        Point p = new Point(0,0);
        Deque<Point> de = new ArrayDeque<Point>();
        boolean[][] b = new boolean[rows][cols];
        de.addLast(p);
        int re= 0;
        if(threshold <0) return re;
        b[0][0] = true;
        while(!de.isEmpty()){
            Point t = de.poll();
            re++;
            if(t.x-1 >=0 && t.x-1 <rows && t.y >=0 && t.y<cols && getSum(t.x-1,t.y) <=threshold &&!b[t.x-1][t.y]) 
            {
                de.addLast(new Point(t.x-1,t.y));
                b[t.x-1][t.y] = true;
            }
            if(t.x+1 >=0 && t.x+1 <rows && t.y >=0 && t.y<cols && !b[t.x+1][t.y] && getSum(t.x+1,t.y) <=threshold) 
            {
                de.addLast(new Point(t.x+1,t.y));
                b[t.x+1][t.y] = true;
            }
            if(t.x >=0 && t.x <rows && t.y+1 >=0 && t.y+1<cols && !b[t.x][t.y+1] && getSum(t.x,t.y+1) <=threshold) 
            {
                de.addLast(new Point(t.x,t.y+1));
                b[t.x][t.y+1] = true;
            }
            if(t.x >=0 && t.x <rows && t.y-1 >=0 && t.y-1<cols &&  !b[t.x][t.y-1] && getSum(t.x,t.y-1) <=threshold) 
            {
                de.addLast(new Point(t.x,t.y-1));
                b[t.x][t.y-1] = true;
            }
        }
        return re;
    }
    private int getSum(int a,int b){
        int re = 0;
        while(a!=0) {
            re+=a%10;
            a = a/10;
        }
        while(b!=0){
            re+=b%10;
            b = b/10;
        }
        return re;
    }
}

function movingCount(threshold, rows, cols)
{
    // write code here
    if(!threshold)return 1;
    if(!rows||!cols)return 0;
    var visited = [];
    var temp = [];
    var i, j;
    var count = {count:0};
    for (i = 0; i < rows; i++) {
      temp = [];
      for (j = 0; j < cols; j++) {
        temp.push(false);
      }
      visited.push(temp);
    }
    move(threshold, rows, cols, 0, 0, count, visited);
    return count.count;
}

function move(threshold, rows, cols, row, col, count, visited) {
    var isMove = false;
    if(rows>row&&cols>col&&col>=0&&row>=0&&!visited[row][col]) {
       if(bitSum(row) + bitSum(col) <= threshold) {
           visited[row][col] = true;
           count.count++;
           move(threshold, rows, cols, row+1, col, count, visited);
           move(threshold, rows, cols, row-1, col, count, visited);
           move(threshold, rows, cols, row, col-1, count, visited);
           move(threshold, rows, cols, row, col+1, count, visited);
       }
    }
    return isMove;
}

function bitSum(num) {
    var sum = 0;
    while(num) {
        sum+=num%10;
        num = parseInt(num/10)
    }
    return sum;
}

module.exports = {
    movingCount : movingCount
};

public class Solution {
    int rows,cols,k,result;
    int movingCount(int threshold, int rows, int cols)
    {
        if(rows<=0||cols<=0||threshold<0) return 0;
        this.rows = rows;
        this.cols = cols;
        this.k    = threshold;
        boolean[][] visited = new boolean[rows][cols];
        help(0,0,visited);
        return result;
    }
    
    public void help(int i,int j, boolean[][] visited){
        if(i<0||i>=rows) return;//不符合要求的i和j直接返回
        if(j<0||j>=cols) return;
        if(visited[i][j]) return;//访问过该方格，直接返回
        visited[i][j] = true;//表明该方格已经访问过了
        int bitSum = 0;
        for(int temp=i,step=2;step-->0;temp=j){//判断位数和是否符合要求
            while(temp>0){
                bitSum += temp%10;
                temp /= 10;
            }
        }
        if(bitSum<=k){
            result++;
            help(i,j-1,visited);//往左
            help(i+1,j,visited);//往下
            help(i,j+1,visited);//往右
            help(i-1,j,visited);//往上
        }
    }
}

class Solution {
private:
    int m_nRows;
    int m_nCols;
    int m_nThreshold;
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int count = 0;
        bool * bVisited = new bool[rows*cols];
        memset(bVisited, false,rows*cols);
        m_nRows = rows;
        m_nCols = cols;
        m_nThreshold = threshold;
        movingCountHelper(bVisited,0,0,count);
        delete [] bVisited;
        return count;
    }

private:
    void movingCountHelper(bool * bVisited,int x,int y,int & count){
        if (x<0||x>=m_nRows||y<0||y>=m_nCols)
            return ;
        if (bVisited[getPosition(x,y)]){
            return ;
        }
        if (canBeVisited(x,y)){
            bVisited[getPosition(x,y)] = true;
            count++;
            movingCountHelper(bVisited,x-1,y,count);
            movingCountHelper(bVisited,x+1,y,count);
            movingCountHelper(bVisited,x,y-1,count);
            movingCountHelper(bVisited,x,y+1,count);
        }
    }
private :
    bool canBeVisited(int x,int y){
        int count = 0;
        while (x!=0){
            count+=(x%10);
            x/=10;
        }
        while (y!=0){
            count+=(y%10);
            y/=10;
        }
        return count<=m_nThreshold;
    }
    inline int getPosition(int x,int y){
        return  x*(m_nCols)+y;
    }

};

分析：
用回溯法实现，从起点出发，从每个点的左右上下开始寻找，如果任何一个方向
已经寻找过或者超出边界或者不满足条件，则停止这个方向的寻找，从另外一个
方向开始寻找每次满足条件，则满足条件个数+1，这样一直找，直到没有满足条
件的点，用栈来存储满足条件的点
class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
  if(threshold<=0||rows<0||cols<0)
   return 0;
  int count=1;
  st1.push(0);
  st2.push(0);
  int x,y;
  bool *flag=new bool[rows*cols]();
  flag[0]=true;
  while(!st1.empty()&&!st2.empty())
  {
   x=st1.top();
   y=st2.top();
   if((x-1)>=0&&!flag[(x-1)*cols+y]&&checkMove(threshold,x-1,y))
   {
    count++;
    flag[(x-1)*cols+y]=true;
    st1.push(x-1);
    st2.push(y);
    continue;
   }
   if((x+1)<rows&&!flag[(x+1)*cols+y]&&checkMove(threshold,x+1,y))
   {
    count++;
    flag[(x+1)*cols+y]=true;
    st1.push(x+1);
    st2.push(y);
    continue;
   }
   if((y-1)>=0&&!flag[x*cols+y-1]&&checkMove(threshold,x,y-1))
   {
    count++;
    flag[x*cols+y-1]=true;
    st1.push(x);
    st2.push(y-1);
    continue;
   }
   if((y+1)<cols&&!flag[x*cols+y+1]&&checkMove(threshold,x,y+1))
   {
    count++;
    flag[x*cols+y+1]=true;
    st1.push(x);
    st2.push(y+1);
    continue;
   }
   st1.pop();
   st2.pop();
  }
  return count;
    }
 bool checkMove(int threshold,int rows,int cols)
 {
  int sum=0;
  while(rows!=0)
  {
   sum+=rows%10;
   rows/=10;
  }
  while(cols!=0)
  {
   sum+=cols%10;
   cols/=10;
  }
  if(sum>threshold)
   return false;
  else
   return true;
 }
 stack<int> st1,st2;
};