题解 | #机器人的运动范围#

#include <string>
#include <utility>

class Solution {
  public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};


    bool vis[101][101] = {false};
    bool ans_v[101][101]={false};
    // typedef struct the_point {
    //     int x;
    //     int y;
    //     the_point() {};
    //     the_point(int _x, int _y): x(_x), y(_y) {}
    //     bool operator<(const the_point& n) const {
    //         return x < n.x;
    //     }


    // };

    // set<the_point>see_set;
    set< pair<int, int> >new_set;

    int number_bit(int x) {
        // x=20;
        string tmpstr = to_string(x);
        int sum = 0;
        for (int i = 0; i < tmpstr.size(); i++) {
            sum += tmpstr[i] - '0';
        }
        // cout << x << " 的数位和为：" << sum << endl;
        return sum;
    }
    int dfs(int threshold, int cur_row, int cur_col, int rows, int cols) {
        if (cur_row < 0 || cur_row >= rows || cur_col < 0 || cur_col >= cols ||
                vis[cur_row][cur_col] ||
                number_bit(cur_row) + number_bit(cur_col) > threshold) {
            return -1;
        }
        vis[cur_row][cur_col] = true;
        // the_point tmp_point{cur_row, cur_col};
        // see_set.insert(tmp_point);
        // new_set.insert(make_pair(cur_row, cur_col));
        ans_v[cur_row][cur_col] = true;
        // cout << tmp_point.x << " " << tmp_point.y << endl;

        for (int i = 0; i < 4; i++) {
            int next_rows = cur_row + dx[i];
            int next_cols = cur_col + dy[i];

            dfs(threshold, next_rows, next_cols, rows, cols);
        }
        // vis[cur_row][cur_col] = false;
        return 0;
    }
    int movingCount(int threshold, int rows, int cols) {
        dfs( threshold, 0, 0,  rows,  cols);
        int cnt =0;
        for (int i=0; i<101; i++) {
            for (int j=0; j<101; j++) {
                if(ans_v[i][j])
                cnt++;
            }
        }
        return cnt;
    }
};

本题：其实无需回溯，这样会加大运行时间，导致过不去，当我注释掉 //vis[]时//
  便通过了，对结果也无影响。
  
  另外：本题也暴露了我的set集合不熟悉，当插入typedef时，需要在里面写一个  
  //     bool operator<(const the_point& n) const {
    //         return x < n.x;
    //     }
	没写就报错了。