题目

代码

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n, w[N][N];
int dist[N][N];struct pll
{int x, y;
};int bfs()
{memset(dist, 0x3f, sizeof dist);queue<pll> q;q.push({0, 0});dist[0][0] = 0;while (q.size()){pll u = q.front();q.pop();int x = u.x, y = u.y;if (x + 1 < n && dist[x + 1][y] > dist[x][y] + 1){dist[x + 1][y] = dist[x][y] + 1;q.push({x + 1, y});}if (y + 1 < n && dist[x][y + 1] > dist[x][y] + 1){dist[x][y + 1] = dist[x][y] + 1;q.push({x, y + 1});}for(int j = y-1; j >= 0 && w[x][j] < w[x][j+1]; j--)if (dist[x][j] > dist[x][y] + 1){dist[x][j] = dist[x][y] + 1;q.push({x, j});}for(int j = y+1; j < n && w[x][j] < w[x][j-1]; j++)if (dist[x][j] > dist[x][y] + 1){dist[x][j] = dist[x][y] + 1;q.push({x, j});}}return dist[n - 1][n - 1];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> w[i][j];cout << bfs();
}

抓住边都是1