方法
将问题看作一个树的遍历筛选问题,起始位置为[0,0],可选路径向左,向下遍历
,通过条件坐标的数位和小于<k.
通过类似中序遍历,来遍历所有可能的坐标点,通过条件限定遍历节点
// 判断当前节点是否符合条件int avaliable(int i, int j,int m,int n, int k){int i_n = 0, j_n = 0;while (i != 0){i_n += i % 10;i = i / 10;}while (j != 0){j_n += j % 10;j = j / 10;}if (i_n + j_n <= k)return 1;else{return 0;}}// 递归遍历节点int count_num(int i, int j, int count, int m, int n, int k, int** visited){if (i < 0 || j < 0 || i >= m || j >= n||visited[i][j]==true)return count;if (avaliable(i, j,m,n ,k)) //若条件满足,进入节点,并检查向左,向下的坐标{visited[i][j] = true;count++; //当前节点满足,计数加1count = count_num(i, j + 1, count, m, n, k, visited);count = count_num(i + 1, j, count, m, n, k, visited);}return count;}//初始化位置,及标记矩阵表示是否visitedint movingCount(int m, int n, int k) {int i = 0, j = 0;int count = 0;int** visited = (int**)malloc(m*sizeof(int*));for (int i = 0; i < m; i++) {visited[i] = (int*)malloc(n*sizeof(int));}return count_num(i, j, count, m, n, k, visited);}