思路就是每次找到当前5个点(自己+周围)中的最小值位置,如果不是自己那么将最小值位置递归判断
C++ 代码
// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b){
if(a[0] != b[0]) return a[0] < b[0];
else return a[3] < b[3];
}
vector<int> judge(int n, int x, int y, int sx[], int sy[]){
vector< vector<int> > t;
t.push_back({query(x,y), x, y, 1});
for(int i=0; i<4; i++){
int xx = x + sx[i];
int yy = y + sy[i];
if(xx < n && xx >= 0 && yy < n && yy >= 0){
t.push_back({query(xx,yy), xx, yy, 0});
}
}
sort(t.begin(), t.end(), cmp);
return t[0];
}
vector<int> getMinimumValue(int n) {
int sx[4] = {0, -1, 0, 1};
int sy[4] = {-1, 0, 1, 0};
int x = 0;
int y = 0;
while(1){
vector<int> ans = judge(n, x, y, sx, sy);
if(ans[1] == x && ans[2] == y) return {x,y};
else{
x = ans[1];
y = ans[2];
}
}
}
};