地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0～m?1 和 0～n?1。
一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
样例1输入：k=7, m=4, n=5
输出：20
样例2输入：k=18, m=40, n=40
输出：1484
解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
0<=m<=50
0<=n<=50
0<=k<=100
搜索的模板题，用一个bool数组g[][]维护方格能否到达，方格可以到达的条件是：在范围内、坐标的数位之和小于等于k。可以先对坐标数位之和进行预处理，使用bfs或dfs进行遍历，用ans表示可以进入的方格数量，每进入一个，ans++。
#include <bits/stdc++.h> using namespace std; bool g[60][60]; int n, m, k, ans; typedef pair<int, int> P; int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int main(){ cin >> k >> m >> n; memset(g, false, sizeof(g)); for(int i=0; i<m; i++) for(int j=0; j<n; j++){ g[i][j] = true; int x = i, y = j; int t = 0; while(x){ t += x%10; x /= 10; } while(y){ t += y%10; y /= 10; } if(t>k) // 预处理 g[i][j] = false; } queue<P> q; q.push((P){0, 0}); g[0][0] = false; ans = 1; while(!q.empty()){ P u = q.front(); q.pop(); for(int i=0; i<4; i++){ int tx = u.first+d[i][0]; int ty = u.second+d[i][1]; if(g[tx][ty] && tx>=0 && tx<m && ty>=0 && ty<n){ ans++; g[tx][ty] = false; q.push((P){tx, ty}); } } } cout << ans; return 0; }标签：
原文地址：https://www.cnblogs.com/gdgzliu/p/11619472.html