题目描述
- 地上有一个m行和n列的方格。
- 一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于
k的格子。 - 例如，当 k 为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
题目解读
- 接着上一篇继续深挖这道题目
上一篇是考虑机器人可以回退的情况，本篇呢，我们不考虑机器人可以回退的情况，即机器人只能向前，不能回退(不能走已经走过的格子)，这种情况下最多能走多少个格子?- 比如四个小方格，坐标为(0,0)、(0,1)、(1,0)、(1,1)，只考虑只能向前走，如果不考虑机器人回退的话，即只能走(0, 0),(0, 1) 或者 (0,0),(1,0)这两条路，无论哪个方向机器人最多走两个格子.
代码
- 代码有两种实现方式 <二维数组 vs 一维数组>
一、将二维格子存放在二维数组中
#include<iostream>
#include<string.h>
using namespace std;
#define threshold 3
#define rows 5
#define cols 5
class Solution {
public:
int add_row_col(int loc){
int tt = 0;
while(loc > 0){
tt += loc%10;
loc /= 10;
}
return tt;
}
int movingCountCore(int row, int col, int visited[][cols]){
int a[4];
// a[0] = 0;
// a[1] = 0;
// a[2] = 0;
// a[3] = 0;
memset(a, 0, 4*sizeof(int));
int result = -1;
if(visited[row][col]==0 && add_row_col(row) + add_row_col(col) <= threshold){
visited[row][col] = 1;
// 上
if(row > 0){
a[0] = movingCountCore(row-1, col, visited);
}
// 下
if(row < rows-1){
a[1] = movingCountCore(row+1, col, visited);
}
// 左
if(col > 0){
a[2] = movingCountCore(row, col-1, visited);
}
// 右
if(col < cols-1){
a[3] = movingCountCore(row, col+1, visited);
}
for(int i=0; i < 4; i++){
if(result < a[i]){
result = a[i];
}
}
result += 1;
}
else{
result = 0;
}
return result;
}
int movingCount(){
int visited[rows][cols];
for(int i=0; i < rows; i++){
for(int j=0; j < cols; j++){
visited[i][j] = 0;
}
}
return movingCountCore(0, 0, visited);
}
};
int main()
{
Solution ss;
cout<<ss.movingCount()<<endl;
}
二、将二维格子存放在一维数组中
#include<iostream>
#include<string.h>
using namespace std;
class Solution {
public:
int add_row_col(int loc){
int tt = 0;
while(loc > 0){
tt += loc%10;
loc /= 10;
}
return tt;
}
int movingCountCore(int threshold, int rows, int cols, int row, int col, int *visited){
int a[4];
int result = 0;
memset(a, 0, 4*sizeof(int));
if(visited[row * cols + col] == 0 && add_row_col(row) + add_row_col(col) <= threshold){
visited[row * cols + col] = 1;
// 上
if(row > 0){
a[0] = movingCountCore(threshold, rows, cols, row-1, col, visited);
}
// 下
if(row < rows-1){
a[1] = movingCountCore(threshold, rows, cols, row+1, col, visited);
}
// 左
if(col > 0){
a[2] = movingCountCore(threshold, rows, cols, row, col-1, visited);
}
// 右
if(col < cols-1){
a[3] = movingCountCore(threshold, rows, cols, row, col+1, visited);
}
for(int i=0; i < 4; i++){
if(result < a[i]){
result = a[i];
}
}
result += 1;
}
else{
result = 0;
}
return result;
}
int movingCount(int threshold, int rows, int cols){
if(threshold < 0 || rows <= 0 || cols <= 0){
return 0;
}
int visited[rows*cols];
memset(visited, 0, sizeof(int)*rows*cols);
return movingCountCore(threshold, rows, cols, 0, 0, visited);
}
};
int main()
{
Solution ss;
int threshold = 5;
int rows = 10;
int cols = 10;
cout<<ss.movingCount(threshold, rows, cols)<<endl;
}
-
考虑 threshold = 3, rows = 5, cols = 5 的情况，可得机器人的一条前进路线如图所示(最长路线不唯一)，共计 8
总结展望
- 多思考、多总结、多反思。
- 将两者对比思考，将会发现两者实现思路何其相似，改动也不大，但是实现的任何是不同的.
- 有点游戏的编程感觉在其中，比如遇到墙不能走之类的...
