AcWing 15. 二维数组中的查找-DFS
原题链接
中等
作者:
NoisyCat
,
2021-01-21 23:27:39
,
所有人可见
,
阅读 419
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
int n = array.size();
if(!n) return false;
int m = array[0].size();
vector<vector<bool>> st(n, vector<bool>(m, false));
return dfs(array, st, target, 0, 0); // 从左上角即最小的点开始搜索
}
bool dfs(const vector<vector<int>>& array, vector<vector<bool>>& st, int target, int i, int j){
st[i][j] = true;
if(array[i][j] > target) return false;
if(array[i][j] == target) return true;
bool right = false, down = false;
// 每次把当前点的右边和下边加入到搜索中
if(i+1<array.size() && !st[i+1][j]) right = dfs(array, st, target, i+1, j);
if(j+1<array[0].size() && !st[i][j+1]) down = dfs(array, st, target, i, j+1);
return right||down;
}
};