首页 > 试题广场 >

机器人移动范围

[编程题]机器人移动范围
  • 热度指数:4496 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
地上有一个 m 行和 n 列的方格。一个机器人从坐标 0,0 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 k 的格子。 例如,当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7 = 18 。但是,它不能进入方格(35,38),因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子?

数据范围:

输入描述:
一行三个正整数由空格分开,分别代表行数 m ,列数 n ,和坐标数位之和的阈值 k 。


输出描述:
一个正整数,代表该机器人能够到达的格子数量。
示例1

输入

3 3 6

输出

9
示例2

输入

1 1 1

输出

1
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))
发表于 2019-10-15 23:54:21 回复(0)
题目表述有问题吧???也不说是一次性?还是什么
发表于 2019-09-20 11:18:28 回复(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)