地上有一个 m 行和 n 列的方格。一个机器人从坐标 0,0 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如，当 k 为 18 时，机器人能够进入方格（35,37），因为 3+5+3+7 = 18 。但是，它不能进入方格（35,38），因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
数据范围： 
， 
[编程题]机器人移动范围
import java.util.*;
public class Main{
public static int count=0;
public static void main(String[] args){
Scanner sc =new Scanner(System.in);
String[] strs =sc.nextLine().split(" ");
int m = Integer.parseInt(strs[0]);
int n = Integer.parseInt(strs[1]);
int k = Integer.parseInt(strs[2]);
int[][] map =new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(numSum(i,j)>k){
map[i][j]=-1;
}else{
map[i][j]=0;
}
}
}
moveHelper(map,0,0);
System.out.println(count);
}
public static void moveHelper(int[][] map,int i,int j){
if(i<0||i>=map.length||j<0||j>=map[0].length||map[i][j]==-1)return;
count++;
map[i][j]=-1;
moveHelper(map,i+1,j);
moveHelper(map,i-1,j);
moveHelper(map,i,j+1);
moveHelper(map,i,j-1);
}
public static int numSum(int i,int j){
int sum=0;
while(i!=0){
sum+=(i%10);
i=i/10;
}
while(j!=0){
sum+=(j%10);
j=j/10;
}
return sum;
}
}
发表于 2020-06-29 17:43:12
回复(0)
#include <bits/stdc++.h>
using namespace std;
int m,n,k,s=0;
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
struct P{
int x,y;
};
int F(int x){
int t=0;
while(x){
t += x%10;
x /= 10;
}
return t;
}
void BFS(int sx, int sy){
bool vis[m][n];
memset(vis,false,sizeof(vis));
queue<P> q;
q.push({sx,sy});
vis[sx][sy] = true;
s++;
while(!q.empty()){
P p = q.front();
q.pop();
for(int i=0;i<4;i++){
int xx = p.x + dir[i][0];
int yy = p.y + dir[i][1];
if(xx>=0 && xx<m && yy>=0 && yy<n && !vis[xx][yy] && F(xx)+F(yy)<=k){
s++;
q.push({xx,yy});
vis[xx][yy] = true;
}
}
}
return;
}
int main(){
cin>>m>>n>>k;
BFS(0,0);
cout<<s<<endl;
return 0;
}
发表于 2019-09-08 10:59:21
回复(1)
#include <iostream>
using namespace std;
int getDigitSum(int number)
{
int sum=0;
while(number>0)
{
sum+=number%10;
number=number/10;
}
return sum;
}
bool check(int threshold,int rows,int cols,int row,int col,bool* visited)
{
if(row>=0&&row<rows&&col>=0&&col<cols\
&&getDigitSum(row)+getDigitSum(col)<=threshold\
&&!visited[row*cols+col])
return true;
return false;
}
int movingCountCore(int threshold,int rows,int cols,int row,int col,bool* visited)
{
int count=0;
if(check(threshold,rows,cols,row,col,visited))
{
visited[row*cols+col]=true;
count=1+movingCountCore(threshold,rows,cols,row-1,col,visited)+\
movingCountCore(threshold,rows,cols,row,col-1,visited)+\
movingCountCore(threshold,rows,cols,row+1,col,visited)+\
movingCountCore(threshold,rows,cols,row,col+1,visited);
}
return count;
}
int main(){
int rows,cols,threshold;
cin>>rows>>cols>>threshold;
if(threshold<0||rows<=0||cols<=0){
cout<<0;
return 0;
}
bool* visited = new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
visited[i]=false;
int count = movingCountCore(threshold,rows,cols,0,0,visited);
cout<<count;
delete[] visited;
return 0;
}
发表于 2019-09-05 11:46:20
回复(0)
#include <bits/stdc++.h>
using namespace std;
int mark[110][110];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int ret;
bool check(int x, int y, int n, int m, int k) {
int sum = 0;
int xx = x, yy = y;
while (xx > 0) {
sum += xx % 10;
xx /= 10;
}
while (yy > 0) {
sum += yy % 10;
yy /= 10;
}
return (x >= 0 && x < n && y >= 0 && y < m && sum <= k);
}
void dfs(int x, int y, int n, int m, int k) {
ret++;
mark[x][y] = 1;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (check(xx, yy, n, m, k) && !mark[xx][yy]) {
dfs(xx, yy, n, m, k);
}
}
}
int main() {
int n, m, k;
cin >> n >> m >> k;
ret = 0;
dfs(0, 0, n, m, k);
cout << ret << "\n";
return 0;
}
发表于 2019-11-29 08:44:24
回复(0)
package main
import (
"fmt"
)
func main() {
var m,n,k int
fmt.Scan(&m,&n,&k)
mat:=make([][]int,m)
for i,_:=range mat{
mat[i]=make([]int,n)
}
ans:=0
var dfs func(int,int)
dfs=func(i,j int){
if i<0||i>=m||j<0||j>=n||mat[i][j]==1||calc(i,j)>k{
return
}
mat[i][j]=1
ans++
dfs(i+1,j)
dfs(i,j+1)
dfs(i-1,j)
dfs(i,j-1)
}
dfs(0,0)
fmt.Print(ans)
}
func calc(i,j int)int{
ans:=0
for i>0{
ans+=i%10
i/=10
}
for j>0{
ans+=j%10
j/=10
}
return ans
}
发表于 2023-03-22 16:55:24
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] numStr = sc.nextLine().split(" ");
int m = Integer.valueOf(numStr[0]);
int n = Integer.valueOf(numStr[1]);
int k = Integer.valueOf(numStr[2]);
int[][] grid = new int[m][n];
int nums = dfs(grid, 0, 0, m, n, k);
System.out.println(nums);
}
public static int dfs(int[][] grid, int row, int col, int m, int n, int k) {
if (row < 0 || row >= m || col < 0 || col >= n) return 0;
if (getSum(row) + getSum(col) > k || grid[row][col] == 1) return 0;
grid[row][col] = 1;
return 1 + dfs(grid, row - 1, col, m, n, k)
+ dfs(grid, row + 1, col, m, n, k)
+ dfs(grid, row, col - 1, m, n, k)
+ dfs(grid, row, col + 1, m, n, k);
}
public static int getSum(int point) {
int sum = 0;
while (point != 0) {
sum += (point % 10);
point /= 10;
}
return sum;
}
}
发表于 2022-08-28 09:41:13
回复(0)
const [m,n,k] = readline().split(' ').map(Number);
let arr= new Array(m).fill(0).map(c => new Array(n).fill(0));
let count = 0;
dfs(0,0);
function dfs(i,j){
if(i<0 || i>=m || j<0||j>=n || arr[i][j]===1) return;
if((i.toString()+j.toString()).split('').reduce((pre,cur) => Number(pre)+Number(cur))>k){
return;
}
count++;
arr[i][j] = 1;
dfs(i+1,j)
dfs(i,j+1)
dfs(i-1,j)
dfs(i,j-1)
}
console.log(count);
发表于 2022-08-27 17:19:04
回复(0)
bfs
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
bool check(pair<int,int>& pos, int k)
{
int x = pos.first, y = pos.second;
int res = 0;
while (x)
{
res += x%10;
x /= 10;
}
while (y)
{
res += y%10;
y /= 10;
}
return res <= k;
}
int main()
{
int m, n, k;
scanf("%d%d%d", &m, &n, &k);
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<pair<int,int>> Q;
const int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
Q.push({0,0});
visited[0][0] = true;
int ans = 0;
while (!Q.empty())
{
pair<int,int> pos = Q.front();
Q.pop();
if (check(pos, k))
{
ans++;
for (int d = 0; d < 4; ++d)
{
int newx = pos.first+dx[d], newy = pos.second+dy[d];
if (newx<0||newx>=n||newy<0||newy>=m||visited[newy][newx])
continue;
visited[newy][newx] = true;
Q.push({newx, newy});
}
}
}
printf("%d\n", ans);
return 0;
}
发表于 2021-01-13 08:15:40
回复(0)
这道题不能用深度优先，迷宫很大的时候会一直往下递归，造成python递归爆炸，要用广度优先
def check(x, y, k): string = str(x) + str(y) ans = 0 for c in string: ans += int(c) return True if ans <= k else False def BFS(x, y): while queue: node = queue.pop(0) x,y = node[0], node[1] for dx, dy in direction: i = dx + x j = dy + y if 0 <= i < len(maze) and 0 <= j < len(maze[0]): if maze[i][j] == 0 and check(i, j, k): maze[i][j] = 1 queue.append((i,j)) nmk = list(map(int, input().split())) n, m, k = nmk[0], nmk[1], nmk[2] maze = [[0] * n for i in range(m)] direction = [(1, 0), (-1, 0), (0, -1), (0, 1)] queue = [(0,0)] maze[0][0] = 1 BFS(0, 0) ans = 0 for item in maze: ans += sum(item) print(ans)
发表于 2020-08-26 15:24:42
回复(0)
我这个还有哪种特例没有解决嘛 case通过80% 说数组越界 求大佬们解答呀
m,n,k = list(map(int,input().split(' ')))
class Solution:
def Sum(self,x):
S = 0
while x > 0:
S += x%10
x //= 10
return S
def heCanEnterTheBox(self,row,col,rows,cols,threshold,visited):
cnt = 0
if (0<=row<rows and 0<=col<cols and self.Sum(row)+self.Sum(col)<=threshold
and visited[row*cols+col]==False):
visited[row*cols+col] = True
cnt += (1+self.heCanEnterTheBox(row+1, col, rows, cols, threshold,visited)+
self.heCanEnterTheBox(row-1, col, rows, cols, threshold,visited)+
self.heCanEnterTheBox(row, col+1, rows, cols, threshold,visited)+
self.heCanEnterTheBox(row, col-1, rows, cols, threshold,visited))
return cnt
def heCanEnterXBoxes(self,rows,cols,threshold):
if rows <=0&nbs***bsp;cols <= 0&nbs***bsp;threshold < 0:
return 0
visited = [False]*rows*cols
return self.heCanEnterTheBox(0, 0, rows, cols, threshold,visited)
print(Solution().heCanEnterXBoxes(m,n,k))
发表于 2020-06-16 12:16:36
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
rows = sc.nextInt();
cols = sc.nextInt();
int k = sc.nextInt();
System.out.println(movingCount(k, rows, cols));
sc.close();
}
public static int movingCount(int threshold, int rows, int cols)
{
int[][] map = new int[rows][cols];
return helper(map, 0, 0, threshold);
}
private static int rows;
private static int cols;
private static int helper(int[][] map, int i, int j, int k) {
if (i >= rows || j >= cols || checkDigitSum(i) + checkDigitSum(j) > k || map[i][j] == 1)
return 0;
map[i][j] = 1;
return 1+helper(map, i+1, j, k) + helper(map, i, j+1, k);
}
private static int checkDigitSum(int i) {
int ans = 0;
while (i != 0) {
ans += i % 10;
i = i / 10;
}
return ans;
}
}
发表于 2020-06-09 21:49:01
回复(0)
import java.util.*;
public class Main{
private static int[][] step={{0,1},{-1,0},{0,-1},{1,0}};
private static int cnt=0;
private static boolean isBigger(int r,int c,int k)
{
int res=0;
while(r>0)
{
res+=r%10;
r/=10;
}
while(c>0)
{
res+=c%10;
c/=10;
}
if(res>k)
return true;
return false;
}
public static void backTrack(int i,int j,int k,int rows,int cols,boolean[][] mark){
if(i>=rows||i<0||j>=cols||j<0||mark[i][j])
return;
mark[i][j]=true;
if(isBigger(i,j,k))
return;
cnt++;
for(int[] n:step)
backTrack(i+n[0],j+n[1],k,rows,cols,mark);
}
public static void main(String args[]){
Scanner scan=new Scanner(System.in);
int m=scan.nextInt();
int n=scan.nextInt();
int k=scan.nextInt();
boolean[][] mark=new boolean[m][n];
backTrack(0,0,k,m,n,mark);
System.out.println(cnt);
}
}
发表于 2020-05-26 15:35:03
回复(0)
dfs
import java.util.Scanner;
/**
* @Author: coderjjp
* @Date: 2020-05-10 9:52
* @Description:
* @version: 1.0
*/
public class Main {
static int res;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int k = sc.nextInt();
boolean flag[][] = new boolean[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
flag[i][j] = canArrive(i, j, k);
dfs(flag, 0 ,0, m - 1, n - 1);
System.out.println(res);
}
private static void dfs(boolean[][] flag, int x, int y, int m, int n) {
if (!flag[x][y]) return;
res++;
flag[x][y] = false;
if (y > 0) dfs(flag, x, y - 1, m, n);//<--
if (y < n) dfs(flag, x, y + 1, m, n);//-->
if (x > 0) dfs(flag, x - 1, y, m, n);//up
if (x < m) dfs(flag, x + 1, y, m, n);//down
}
private static boolean canArrive(int i, int j, int k) {
int ans = 0;
while (i > 0){
ans += i%10;
i /= 10;
}
while (j > 0){
ans += j%10;
j /= 10;
}
return ans <= k;
}
}
发表于 2020-05-10 10:13:41
回复(0)
BFS
#include<iostream>
(720)#include<vector>
#include<queue>
using namespace std;
bool valid(int x,int y,int m,int n)
{
return x>=0 && x<m && y>=0 && y<n;
}
int get(int x)
{
int ans=0;
while(x)
{
ans+=x%10;
x/=10;
}
return ans;
}
int MovingCount(int m,int n,int k)
{
if(!k)
return 1;
int dx[2]={0,1},dy[2]={1,0};
queue<pair<int,int>>Q;
vector<vector<bool>>vis(m,vector<bool>(n,false));
Q.push({0,0});
vis[0][0]=true;
int res=1;
while(!Q.empty())
{
auto temp=Q.front();
Q.pop();
for(int i=0;i<2;i++)
{
int x=temp.first+dx[i],y=temp.second+dy[i];
if(valid(x,y,m,n) && !vis[x][y] && get(x)+get(y)<=k)
{
res++;
Q.push({x,y});
vis[x][y]=true;
}
}
}
return res;
}
int main()
{
int m,n,k;
while(cin>>m>>n>>k)
{
int res=MovingCount(m,n,k);
cout<<res<<endl;
}
return 0;
}
发表于 2020-04-20 20:02:47
回复(0)
我一直想的是，机器人能够到达的格子不就是满足数位和小于等于k的所有格子吗，为什么要这么复杂呢。。。。求大神讲解
发表于 2020-04-08 20:39:52
回复(2)
广度遍历的思想
#include <iostream>
(720)#include <queue>
using namesapce std;
int NumFit(int x)
{
int sum = 0;
while (x)
{
sum += x % 10;
x /= 10;
}
return sum;
}
struct XY
{
int x;
int y;
};
bool Check(int x, int y, int r, int c, int m)
{
if (r < x && c < y)
{
int n = NumFit(r) + NumFit(c);
if (n <= m)
return true;
}
return false;
}
int SumAll(int x,int y,int m,bool *flag)
{
queue que;
int sum = 0;
if (!Check(x,y,0,0,m))
{
return -1;
}
que.push({ 0,0 });
flag[0] = true;
while (!que.empty())
{
XY num = que.front();
sum++;
que.pop();
if (Check(x, y, (num.x + 1), num.y, m) && !flag[(num.x +1)*x + num.y])
{
que.push({ (num.x + 1),num.y });
flag[(num.x + 1)*x + num.y] = true;
}
if (Check(x, y, num.x, (num.y + 1), m) && !flag[(num.x)*x + num.y + 1])
{
que.push({ num.x,(num.y + 1) });
flag[(num.x)*x + num.y + 1] = true;
}
}
return sum;
}
int main()
{
int x = 0;
int y = 0;
int m = 0;
cin >> x >> y >> m;
if (x 100 || y > 100 || m > 20)
return -1;
bool *flag = new bool[x * y];
for (int i = 0; i < x*y; ++i)
flag[i] = false;
cout << SumAll(x, y, m, flag) << endl;
delete[]flag;
return 0;
}
发表于 2020-03-21 21:34:41
回复(0)
importjava.util.Scanner;
publicclassMain{
privatestaticintm, n;
privatestaticint[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
publicstaticvoidmain(String[] args){
Scanner sc = newScanner(System.in);
String s = sc.nextLine();
String sub[] = s.split(" ");
m = Integer.valueOf(sub[0]);
n = Integer.valueOf(sub[1]);
intk = Integer.valueOf(sub[2]);
booleanvisited[][] = newboolean[m][n];
intgezi = 1;
intres = getCount(0, 0, k, visited, gezi);
System.out.println(res);
}
privatestaticintgetCount(intmm, intnn, intk, boolean[][] visited, intgezi){
if(mm >= m || mm < 0|| nn >= n || nn < 0|| visited[mm][nn]){
return0;
}
intwei = 0;
String mw = String.valueOf(mm);
String nw = String.valueOf(nn);
for(inti = 0; i < mw.length(); i++){
wei += Integer.valueOf(mw.charAt(i)-'0');
}
for(inti = 0; i < nw.length(); i++){
wei += Integer.valueOf(nw.charAt(i)-'0');
}
if(wei > k){
return0;
}
visited[mm][nn] = true;
//int count = 1;
for(int[] d: direction){
intnextm = mm + d[0];
intnextn = nn + d[1];
gezi = Math.max(gezi, getCount(nextm, nextn, k, visited, gezi + 1));
}
return gezi;
}
}
发表于 2020-03-20 23:06:30
回复(0)
import sys
def movingCount(rows, cols, threshold):
# write code here
x = [[0 for j in range(cols)] for i in range(rows)]
for i in range(rows):
sum = 0
p = i
while p:
sum += p % 10
p = p // 10
for j in range(cols):
q = j
sum1 = sum
while q:
sum1 += q % 10
q = q // 10
x[i][j] = sum1
dfs(x, threshold, 0, 0)
#print(dict)
return len(dict)
def dfs(x, threshold, i, j):
if not (0 <= i < len(x) and 0 <= j < len(x[0])): # 越界
return
if x[i][j] > threshold:
return
if dict.get((i, j)) is not None:
return
dict[(i, j)] = 1
dfs(x, threshold, i - 1, j)
dfs(x, threshold, i + 1, j)
dfs(x, threshold, i, j - 1)
dfs(x, threshold, i, j + 1)
if __name__ == "__main__":
sys.setrecursionlimit(1000000)
dict = {}
arr = sys.stdin.readline().strip().split()
rows, cols,threshold = int(arr[0]), int(arr[1]), int(arr[2])
print(movingCount(rows, cols,threshold))
def movingCount(rows, cols, threshold):
# write code here
x = [[0 for j in range(cols)] for i in range(rows)]
for i in range(rows):
sum = 0
p = i
while p:
sum += p % 10
p = p // 10
for j in range(cols):
q = j
sum1 = sum
while q:
sum1 += q % 10
q = q // 10
x[i][j] = sum1
dfs(x, threshold, 0, 0)
#print(dict)
return len(dict)
def dfs(x, threshold, i, j):
if not (0 <= i < len(x) and 0 <= j < len(x[0])): # 越界
return
if x[i][j] > threshold:
return
if dict.get((i, j)) is not None:
return
dict[(i, j)] = 1
dfs(x, threshold, i - 1, j)
dfs(x, threshold, i + 1, j)
dfs(x, threshold, i, j - 1)
dfs(x, threshold, i, j + 1)
if __name__ == "__main__":
sys.setrecursionlimit(1000000)
dict = {}
arr = sys.stdin.readline().strip().split()
rows, cols,threshold = int(arr[0]), int(arr[1]), int(arr[2])
print(movingCount(rows, cols,threshold))
发表于 2019-10-15 23:54:21
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int movingCount(int threshold, int rows, int cols){
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
if (threshold < 0 || rows < 0 || cols < 0)
return 0;
return searchPath(threshold, rows, cols, visited, 0, 0);
}
int searchPath(int threshold, int rows, int cols, vector<vector<bool>>& visited, int row, int col){
if (row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col] && numPart(row) + numPart(col) <= threshold){
visited[row][col] = true;
return 1
+ searchPath(threshold, rows, cols, visited, row, col - 1)
+ searchPath(threshold, rows, cols, visited, row, col + 1)
+ searchPath(threshold, rows, cols, visited, row - 1, col)
+ searchPath(threshold, rows, cols, visited, row + 1, col);
}
else
return 0;
}
int numPart(int num){
int ans = 0;
while (num > 9){
ans += (num % 10);
num /= 10;
}
return ans + num;
}
};
int main(){
int m, n, k;
cin >> m >> n >> k;
vector<vector<bool>> visited(m, vector<bool>(n, false));
Solution ans;
cout << ans.searchPath(m, n, k, visited, 0, 0) << endl;
return 0;
}
发表于 2019-09-15 17:02:05
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-08-30 20:22:05 -
2022-08-29 09:56:15
-
2022-08-28 09:39:54
-
2022-08-27 17:18:20
-
2022-08-25 02:05:28
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
