Part1. 我的思路和代码(80%)
刚开始感觉和上一个题(12_矩阵中的路径)是一样的,只是判断条件不同,该题是用坐标的数位和判断,于是按照上一题的做法写了代码。思路方面和上一题相仿
:
起点选择: 只有(0, 0)位置。
搜索策略: 目前路径不为空时(为空表示所有路线遍历完毕),如果当前位置满足坐标的数位和条件
,则依次向四个方向搜索一步(注意搜索的下一步不能超过方格边界,并且不能是目前搜索路径上搜索过的位置),否则回溯;同时如果当前位置已经向四个方向都搜索过
,也回溯。
判断条件: 利用%运算
提取每一位的值,计算坐标的数位和,判断是否满足阈值条件,见isAccessable()函数。
变量设置: 同样分为搜索路径信息、辅助标志两部分。前者包括path_rows、path_cols,记录目前搜索路径每个位置的坐标;后者包括flag和visited,都是二维数组,形状和方格区域相同,其中flag和上一题笔记中的作用相同,visited则仅表示是否搜索过
,值为1表示搜索过,0表示没有,最后visited中1的数量即题目所求
。
然而,该做法每个位置不一定只搜索一次,于是时间复杂度不是O(mn),提交后通过80%的用例
。
bool isAccessable(int cur_row, int cur_col, int rows, int cols, int threshold) { // 计算位置数位和,判断指定位置是否可以进入
int sum = 0;
int temp_row = cur_row;
int temp_col = cur_col;
while(temp_row){ // 计算坐标的数位之和
sum += temp_row % 10;
temp_row /= 10;
}
while(temp_col){
sum += temp_col % 10;
temp_col /= 10;
}
if(sum > threshold){
return false;
}
return true;
}
bool isOnCurPath(int row, int col, vector<int>& path_rows, vector<int>& path_cols) { //判断指定位置是否在当前搜索路径中
for(int i=0; i<path_rows.size(); i++){
if(row==path_rows[i] && col==path_cols[i]){
return true;
}
}
return false;
}
int movingCount(int threshold, int rows, int cols) {
int ans = 0;
vector<int> path_rows;
vector<int> path_cols;
vector<vector<int> > flag;
vector<vector<int> > visited;
path_rows.push_back(0); // 初始化
path_cols.push_back(0);
vector<int> tempArr(cols, 0);
for(int i=0; i<rows; i++){
flag.push_back(tempArr);
visited.push_back(tempArr);
}
while(!path_rows.empty()){ // 开始搜索
int cur_row = path_rows.back();
int cur_col = path_cols.back();
if(flag[cur_row][cur_col] == 4){
path_rows.pop_back();
path_cols.pop_back();
flag[cur_row][cur_col] = 0;
if(!path_rows.empty()){
cur_row = path_rows.back();
cur_col = path_cols.back();
}
continue;
}
if(isAccessable(cur_row, cur_col, rows, cols, threshold)){
visited[cur_row][cur_col] = 1;
switch(flag[cur_row][cur_col]){
case 0: // 向左
if(cur_col-1 >= 0 && !isOnCurPath(cur_row, cur_col-1, path_rows, path_cols)){
path_rows.push_back(cur_row);
path_cols.push_back(cur_col-1);
}
++flag[cur_row][cur_col];
break;
case 1: //向上
if(cur_row-1 >= 0 && !isOnCurPath(cur_row-1, cur_col, path_rows, path_cols)){
path_rows.push_back(cur_row-1);
path_cols.push_back(cur_col);
}
++flag[cur_row][cur_col];
break;
case 2: //向右
if(cur_col+1 < cols && !isOnCurPath(cur_row, cur_col+1, path_rows, path_cols)){
path_rows.push_back(cur_row);
path_cols.push_back(cur_col+1);
}
++flag[cur_row][cur_col];
break;
case 3: //向下
if(cur_row+1 < rows && !isOnCurPath(cur_row+1, cur_col, path_rows, path_cols)){
path_rows.push_back(cur_row+1);
path_cols.push_back(cur_col);
}
++flag[cur_row][cur_col];
break;
default:
break;
}
}
else{
path_rows.pop_back();
path_cols.pop_back();
flag[cur_row][cur_col] = 0;
if(!path_rows.empty()){
cur_row = path_rows.back();
cur_col = path_cols.back();
}
}
}
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(visited[i][j] == 1){
++ans;
}
}
}
return ans;
}
Part2. 我的思路和代码(100%)
经过思考,该题和上一个题有所区别,该题更多的是求“能到达的地方”,而不是一条具体的路线(就像洪水一样,计算的是洪水能够到达的地方,而不是洪水的哪股水流以怎样的具体路线碰到了一颗石头
),因此和上一题的DFS不同,此题目用广度优先搜索BFS
。经过调整,代码写法上简洁了许多,搜索策略和变量设置为:
搜索策略: 从起点开始,如果当前坐标满足阈值条件,则向四个方向都搜索一步(超过区域边界或已经搜索到的位置除外),不断“扩散”
。
变量设置: 使用队列
保存当前搜索过的位置信息,每次循环获取队首,它向四个方向搜索到的位置从队尾进入队列,最后队首元素出队,随着不断处理,队列为空时搜索完成。另一方面,由于四个方向都要搜索,于是不需要flag数组区分方向,只需要visited数组标记是否搜索过即可。
每个位置只会搜索一次
,于是时间复杂度为O(mn),通过了所有用例。
bool isAccessable(int cur_row, int cur_col, int rows, int cols, int threshold) { // 计算位置数位和,判断指定位置是否可以进入
int sum = 0;
int temp_row = cur_row;
int temp_col = cur_col;
while(temp_row){ // 计算坐标的数位之和
sum += temp_row % 10;
temp_row /= 10;
}
while(temp_col){
sum += temp_col % 10;
temp_col /= 10;
}
if(sum > threshold){
return false;
}
return true;
}
int movingCount(int threshold, int rows, int cols) {
int ans = 0;
queue<int> path_rows;
queue<int> path_cols;
vector<vector<int> > visited;
path_rows.push(0); // 初始化
path_cols.push(0);
vector<int> tempArr(cols, 0);
for(int i=0; i<rows; i++){
visited.push_back(tempArr);
}
visited[0][0] = 1;
while(!path_rows.empty()){ // 开始搜索
int cur_row = path_rows.front();
int cur_col = path_cols.front();
if(isAccessable(cur_row, cur_col, rows, cols, threshold)){
if(cur_col-1 >= 0 && visited[cur_row][cur_col-1]==0){ //向左
path_rows.push(cur_row);
path_cols.push(cur_col-1);
visited[cur_row][cur_col-1] = 1;
}
if(cur_row-1 >= 0 && visited[cur_row-1][cur_col]==0){ //向上
path_rows.push(cur_row-1);
path_cols.push(cur_col);
visited[cur_row-1][cur_col] = 1;
}
if(cur_col+1 < cols && visited[cur_row][cur_col+1]==0){ //向右
path_rows.push(cur_row);
path_cols.push(cur_col+1);
visited[cur_row][cur_col+1] = 1;
}
if(cur_row+1 < rows && visited[cur_row+1][cur_col]==0){ //向下
path_rows.push(cur_row+1);
path_cols.push(cur_col);
visited[cur_row+1][cur_col] = 1;
}
}
else{
visited[cur_row][cur_col] = 0;
}
path_rows.pop();
path_cols.pop();
}
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(visited[i][j] == 1){
++ans;
}
}
}
return ans;
}
Part3. 其他做法
书上的做法
思路相似,本质上也是BFS,但代码为递归写法
,更加简洁。递归函数返回值为从某个位置开始能到达位置的数量,计算返回值时,对左、上、右、下位置均递归调用函数,将四次递归调用的结果相加,再加1
(当前位置也是一个可以到达的位置)。
Part4. 心得体会
- 这道题标注的是“困难”难度,但做出这道题的时间比上一道少一些,更加体会到
难易是相对的
。 - 遇到和自己以前做过的相似的题目,要注意有什么不同,
照搬原有思路可能并不是最优的选择
。