本文共 1549 字，大约阅读时间需要 5 分钟。

1. 题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 37]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：输入：m = 2, n = 3, k = 1输出：3示例 1：输入：m = 3, n = 1, k = 0输出：1提示：1 <= n,m <= 1000 <= k <= 20

来源：力扣（LeetCode）

2. 解题

2.1 BFS

class Solution {
   public:    int movingCount(int m, int n, int k) {
           vector
   
    
     > visited(m, vector
     
      (n,false));        vector
      
       
        > dir = {
   {
   -1,0},{
   1,0},{
   0,1},{
   0,-1}};        queue
        
         
          > q; q.push({ 0,0}); visited[0][0] = true; int count = 1, tpx, tpy, x, y, i; while(!q.empty()) { tpx = q.front()[0]; tpy = q.front()[1]; q.pop(); for(i = 0; i < 4; ++i) { x = tpx+dir[i][0]; y = tpy+dir[i][1]; if(x>=0 && x
          
           =0 && y
          
         
        
       
      
     
    
   

2.2 DFS

class Solution {
       vector
   
    
     > dir = {
   {
   -1,0},{
   1,0},{
   0,1},{
   0,-1}};public:    int movingCount(int m, int n, int k) {
           vector
     
      
       > visited(m, vector
       
        (n,false));        int count = 1;        visited[0][0] = true;        dfs(0,0,count,visited,m,n,k);        return count;    }    void dfs(int i, int j, int& count, vector
        
         
          >& visited,int& m, int& n, int& k) { int x, y; for(int a = 0; a < 4; ++a) { x = i+dir[a][0]; y = j+dir[a][1]; if(x >=0 && x
          
           =0 && y
          
         
        
       
      
     
    
   

转载地址：https://michael.blog.csdn.net/article/details/104304746 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！