Line data    Source code

       1              : // Copyright (c) 2022 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              : // Created: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <vector>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25            4 :     int movingCount(int m, int n, int k) {
      26            4 :         std::vector<std::vector<int>> visted(m, std::vector<int>(n, 0));
      27            8 :         return dfs(visted, 0, 0, k);
      28            4 :     }
      29              : 
      30              : private:
      31        14718 :     int bitsadd(int i) {
      32        14718 :         int ret = 0;
      33        41339 :         while (i > 0) {
      34        26621 :             ret += i % 10;
      35        26621 :             i /= 10;
      36              :         }
      37        14718 :         return ret;
      38              :     }
      39              : 
      40        22716 :     int dfs(std::vector<std::vector<int>>& visted, int i, int j, int k) {
      41        30075 :         if (i < 0 || i >= visted.size() || j < 0 || j >= visted[0].size() || visted[i][j] == 1 ||
      42         7359 :             bitsadd(i) + bitsadd(j) > k) {
      43        17038 :             return 0;
      44              :         }
      45         5678 :         visted[i][j] = 1;
      46         5678 :         int ret = 1;
      47         5678 :         int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
      48        28390 :         for (int m = 0; m < 4; ++m) {
      49        22712 :             ret += dfs(visted, i + dx[m], j + dy[m], k);
      50              :         }
      51         5678 :         return ret;
      52              :     }
      53              : };
      54              : } // namespace
      55              : 
      56            4 : TEST(Leetcode, ji_qi_ren_de_yun_dong_fan_wei_lcof) {
      57            1 :     Solution s;
      58            1 :     EXPECT_EQ(3, s.movingCount(2, 3, 1));
      59            1 :     EXPECT_EQ(1, s.movingCount(2, 3, 0));
      60            1 :     EXPECT_EQ(309, s.movingCount(100, 100, 10));
      61            1 :     EXPECT_EQ(5365, s.movingCount(100, 100, 19));
      62            1 : }