地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
2024-09-02 13:21:26
// test20.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<string.h>
#include<deque>
#include <forward_list>
using namespace std;
class Solution {
public:
vector<vector<bool>> flag; //访问标志,
int movingCount(int threshold, int rows, int cols)
{
for (int i = 0;i < rows;++i)//没有访问过设置为true
{
vector<bool> vec;
for (int j = 0;j < cols;++j)
{
vec.push_back(false);
}
flag.push_back(vec);
}
return movCount(threshold, rows, cols,0,0) ;
}
//此函数为回溯函数
int movCount(int threshold, int rows, int cols,int i,int j)//访问的是当前的单元
{
if (i < 0 || i >= rows || j < 0 || j >= cols || !LegalOrNot(threshold, i, j) || flag[i][j]) return 0;
flag[i][j] = true;
return movCount(threshold, rows, cols, i - 1, j) +
movCount(threshold, rows, cols, i + 1, j) +
movCount(threshold, rows, cols, i , j-1) +
movCount(threshold, rows, cols, i , j+1) +1;
}
//此函数为来标注该格子是否是合法的,可以允许访问
bool LegalOrNot(int threshold, int row, int col)
{
int num = 0;
while (row != 0)
{
num = num + row % 10;
row = row / 10;
}
while (col != 0)
{
num = num + col % 10;
col = col / 10;
}
if (num <= threshold)
return true;//合法访问
return false;
}
};
int main()
{
Solution so;
//cout << 1 / 10 << endl;
cout << "数量为:" << so.movingCount(10, 1, 100) << endl;
return 0;
}
最新文章
- mysql 5.5 修改字符编码
- avl树的操作证明
- Ajax异步刷新地址栏url改变(利用Html5 history.pushState实现)
- iOS开发 画六边形(多边形)
- c++ 普通高精除高精
- Begin Andriod -- 安装android开发环境
- .NET 解析HTML代码——NSoup
- mysql索引之普通索引
- css伪类伪元素
- Mysql 使用 select into outfile
- java调用oracle数据库发布WebService
- 深入浅出Java探针技术1--基于java agent的字节码增强案例
- Python开发——12.socket编程
- 【强大美观易用的图像编辑器】Pixelmator Pro 1.2 for Mac
- Atitit s2018.6 s6 doc list on com pc.docx Atitit s2018.6 s6 doc list on com pc.docx Aitit algo fix 算法系列补充.docx Atiitt 兼容性提示的艺术 attilax总结.docx Atitit 应用程序容器化总结 v2 s66.docx Atitit file cms api
- Zabbix实战-简易教程--DB类--ClickHouse
- transform 图标旋转,IE8、IE7不兼容
- U3D学习10——关节和射线检测
- jstl <;fmt:formatNumber>;标签
- JS基础(三)
热门文章
- Docker(二):Docker的用途
- 《Linux命令行与shell脚本编程大全 第3版》Linux命令行---33
- DOM-window下的常用子对象-location-刷新页面
- Codeforces Gym100735 G.LCS Revised (KTU Programming Camp (Day 1) Lithuania, Birˇstonas, August 19, 2015)
- CentOS 7下安装配置FTP
- Jenkins强制设置语言为中文
- windows内核实现的34个关键问题
- XCODE 4.5 IOS多语言设置 及NSLocalizedString和NSLocalizedStringFromTable的用法。
- ylb:sql语句重命名表名和列名
- Python--图像处理(2)