題目鏈接

題意

給一個R、C數(shù)字矩陣，每個點(diǎn)可以向上下左右且比自己小的方向移動，問最長移動距離

AC

• dfs + 記憶

#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <map> #include <string.h> #include <cmath> #include <algorithm> #define N 100005 #define P pair<int,int> #define mk(a, b) make_pair(a, b) #define mem(a, b) memset(a, b, sizeof(a)) int inf = 0x3f3f3f3f; #define ll long long6 using namespace std; int r, c; int g[120][120]; int ans; int vis[120][120]; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; bool judge(int x, int y) {if (x < 0 || x >= r || y < 0 || y >= c)return false;elsereturn true; } int dfs(int x, int y) {if (vis[x][y] >= 0) {return vis[x][y];}for (int i = 0; i < 4; ++i) {int nx, ny;nx = x + dx[i];ny = y + dy[i];if (!judge(nx, ny) || g[nx][ny] >= g[x][y]) continue;int temp = dfs(nx, ny) + 1;vis[x][y] = max(vis[x][y], temp);}if (vis[x][y] == -1) return vis[x][y] = 0;else return vis[x][y]; }int main(){while (cin >> r >> c) {for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {cin >> g[i][j];}}ans = -1;mem(vis, -1);for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {ans = max(ans, dfs(i, j) + 1);}}cout << ans << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 1088（滑雪）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。