地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
dfs：
class Solution { public: int sum(int i, int j){ int count = 0; while(i > 0) { count = count + i%10; i = i/10; } while(j > 0) { count = count + j%10; j = j/10; } return count; } int num = 0; int dir[5] = {1, 0, -1, 0, 1}; void dfs(int *&m, int threshold, int rows, int cols, int i, int j){ if(i < 0 || i >= rows || j < 0 || j >= cols || sum(i, j) > threshold || m[i*cols+j] == 1) return; num++; m[i*cols+j] = 1; for(int k = 0; k < 4; k++) dfs(m, threshold, rows, cols, i+dir[k], j+dir[k+1]); } int movingCount(int threshold, int rows, int cols) { int *matrix = new int[rows*cols]; for(int i = 0; i < rows*cols; i++) matrix[i] = 0; dfs(matrix, threshold, rows, cols, 0, 0); return num; } };bfs：
class Solution { public: int sum(int i, int j){ int count = 0; while(i > 0) { count = count + i%10; i = i/10; } while(j > 0) { count = count + j%10; j = j/10; } return count; } int movingCount(int threshold, int rows, int cols) { int num = 0; int dir[5] = {1, 0, -1, 0, 1}; int *matrix = new int[rows*cols]; for(int i = 0; i < rows*cols; i++) matrix[i] = 0; queue<pair<int, int> > q; if(rows > 0 && cols > 0 && threshold >= 0) {q.push({0,0}); matrix[0] = 1;} while(!q.empty()) { pair<int, int> p = q.front(); for(int i = 0; i < 4; i++) { if(sum(p.first+dir[i],p.second+dir[i+1]) <= threshold && \ matrix[(p.first+dir[i])*cols+p.second+dir[i+1]] == 0 && \ p.first+dir[i] >= 0 && p.first+dir[i] < rows && \ p.second+dir[i+1] >= 0 && p.second+dir[i+1] < cols) { q.push({p.first+dir[i],p.second+dir[i+1]}); matrix[(p.first+dir[i])*cols+p.second+dir[i+1]] = 1; } } q.pop(); num++; } return num; } };开二位数组：
int mark[rows][cols]; memset(mark, -1, sizeof(mark));