Line data    Source code

       1              : // Copyright (c) 2024 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : 
      17              : #include <gtest/gtest.h>
      18              : 
      19              : #include <vector>
      20              : 
      21              : namespace {
      22              : class Solution {
      23              : public:
      24            4 :     int movingCount(int m, int n, int k) {
      25            4 :         std::vector<std::vector<int>> visted(m, std::vector<int>(n, 0));
      26            8 :         return dfs(visted, 0, 0, k);
      27            4 :     }
      28              : 
      29              : private:
      30        14718 :     int bitsadd(int i) {
      31        14718 :         int ret = 0;
      32        41339 :         while (i > 0) {
      33        26621 :             ret += i % 10;
      34        26621 :             i /= 10;
      35              :         }
      36        14718 :         return ret;
      37              :     }
      38              : 
      39        22716 :     int dfs(std::vector<std::vector<int>>& visted, int i, int j, int k) {
      40        30075 :         if (i < 0 || i >= visted.size() || j < 0 || j >= visted[0].size() || visted[i][j] == 1 ||
      41         7359 :             bitsadd(i) + bitsadd(j) > k) {
      42        17038 :             return 0;
      43              :         }
      44         5678 :         visted[i][j] = 1;
      45         5678 :         int ret = 1;
      46         5678 :         int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
      47        28390 :         for (int m = 0; m < 4; ++m) {
      48        22712 :             ret += dfs(visted, i + dx[m], j + dy[m], k);
      49              :         }
      50         5678 :         return ret;
      51              :     }
      52              : };
      53              : } // namespace
      54              : 
      55            4 : TEST(Leetcode, ji_qi_ren_de_yun_dong_fan_wei_lcof) {
      56            1 :     Solution s;
      57            1 :     EXPECT_EQ(3, s.movingCount(2, 3, 1));
      58            1 :     EXPECT_EQ(1, s.movingCount(2, 3, 0));
      59            1 :     EXPECT_EQ(309, s.movingCount(100, 100, 10));
      60            1 :     EXPECT_EQ(5365, s.movingCount(100, 100, 19));
      61            1 : }