题解 | 机器人移动范围

#include <iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int countSum(int sum) {
        int count = 0;
        while (sum > 0) {
            count += sum % 10;
            sum /= 10;
        }
        return count;
    }
    
    int dfs(vector<vector<bool>>& map, int m, int n, int M, int N, int k) {
        if (M < 0 || N < 0 || M > m-1 || N > n-1 || countSum(M) + countSum(N) > k || map[M][N]) {
            return 0;
        }
        map[M][N] = true;
        return 1 + dfs(map, m, n, M+1, N, k)
                 + dfs(map, m, n, M, N+1, k)
                 + dfs(map, m, n, M-1, N, k)
                 + dfs(map, m, n, M, N-1, k);
    }
};

int main() {
    int m, n, k;
    Solution sol;
    while (cin >> m >> n >> k) {
        vector<vector<bool>> map(m, vector<bool>(n, false));
        cout << sol.dfs(map, m, n, 0, 0, k) << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    private static int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
    
    private static int dfs(boolean[][] visited, int m, int n, int x, int y, int k) {
        // 检查边界条件
        if (x < 0 || x >= m || y < 0 || y >= n || 
            getDigitSum(x) + getDigitSum(y) > k || visited[x][y]) {
            return 0;
        }
        
        // 标记当前格子并继续搜索
        visited[x][y] = true;
        
        // 向四个方向搜索
        return 1 + dfs(visited, m, n, x + 1, y, k)
                 + dfs(visited, m, n, x - 1, y, k)
                 + dfs(visited, m, n, x, y + 1, k)
                 + dfs(visited, m, n, x, y - 1, k);
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int m = in.nextInt();
            int n = in.nextInt();
            int k = in.nextInt();
            boolean[][] visited = new boolean[m][n];
            System.out.println(dfs(visited, m, n, 0, 0, k));
        }
    }
}

# -*- coding:utf-8 -*-
import sys 

class Solution:
    def getDigitSum(self, num):
        sum = 0
        while num > 0:
            sum += num % 10
            num //= 10
        return sum
    
    def movingCount(self, m, n, k):
        visited = [[False] * n for _ in range(m)]
        # 使用栈来模拟递归
        stack = [(0, 0)]
        count = 0
        
        while stack:
            x, y = stack.pop()
            # 检查边界条件
            if (x < 0 or x >= m or y < 0 or y >= n or 
                self.getDigitSum(x) + self.getDigitSum(y) > k or visited[x][y]):
                continue
            
            # 标记当前格子
            visited[x][y] = True
            count += 1
            
            # 只需要向右和向下搜索即可
            for dx, dy in [(1, 0), (0, 1)]:
                nx, ny = x + dx, y + dy
                stack.append((nx, ny))
        
        return count

# 处理输入
for line in sys.stdin:
    m, n, k = map(int, line.strip().split())
    solution = Solution()
    print(solution.movingCount(m, n, k))