#include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> PII; const int N = 110; int g[N][N]; int d[N][N]; int n, m, l; int bfs() { queue<PII> q; q.push({0,0}); memset(d, -1, sizeof d); //全部设置为-1; d[0][0] = 0; // (0,0)的距离为0; int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1}; //四个方向; while(!q.empty()) { PII t = q.front(); q.pop(); for(int i = 0;i < 4;i ++) { int k = t.first, w = t.second; int x = t.first + dx[i], y = t.second + dy[i]; if(x >= 0 && x < n && y >= 0 && y < m && (g[x][y] - g[k][w] <= l)&& d[x][y] == -1) //g[x][y]为0代表空地,d[x][y]为-1代表没走过; { d[x][y] = d[t.first][t.second] + 1; q.push({x,y}); } } } return d[n - 1][m - 1]; } int main() { int p; cin >> p; while(p --) { cin >> n >> m >> l; for(int i = 0;i < n;i ++) { for(int j = 0;j < m;j ++) { cin >> g[i][j]; } } cout << bfs() << endl; } } |
Double click to view unformatted code.