题目

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：

与上一道的区别是去重计算，最直接的思路是map记录，一开始在想回溯的时候在交叉点处犹豫，担心会不会少算，但当他到达交叉点的时候接下来的所有可能已经被上一个来这里的点搞定了，所以无缺（不会有：上一个点阻止我进入但是有些路径是只有我进入才能到达上一个点进入这里不能探索到 的情况），只要搜索保证吧所以空间都搜到，然后每个搜索都判断非法就好了（只关心当前）。

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> map;
    int k;
    void init(int rows, int cols, int threshold){
        for(int i=0;i<rows;++i){
            vector<int> row;
            for(int j=0;j<cols;++j){
                row.push_back(0);
            }
            map.push_back(row);
        }
        k = threshold;
    }
    int splitSum(int x, int y){
        int sum = 0;
        while(x>0){
            sum += x %10;
            x /= 10;
        }
        while(y>0){
            sum += y % 10;
            y /= 10;
        }
        return sum;
    }
    void move(int x, int y){
        if(x<0||x==map.size()||y<0||y==map[0].size())
            return;
        if(map[x][y]!=0||splitSum(x, y)>k)
            return;
        map[x][y] = 1;   //全覆盖搜索+根据当前情况判断跳出，高效实现搜索
        move(x-1, y);
        move(x, y+1);
        move(x+1, y);
        move(x, y-1);
    }
    int movingCount(int threshold, int rows, int cols)
    {
        init(rows, cols, threshold);
        move(0, 0);
        int sum=0;
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                if(map[i][j]!=0)
                    sum++;
            }
        }
        cout<<sum<<endl;
    }
};

30分钟解决一遍过。难得。