40分求助/cpp/萌新

P1434 [SHOI2002] 滑雪

YangLH @ 2019-09-12 15:55:14

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
inline void test();

int r, c, height[100][100] = {}, rec_dist[100][100] = {}, max_dist = 0;

int bfs(int row, int col, int current_height) {
    if (row<0||col<0||row>=r||col>=c) return 0;
    if (rec_dist[row][col]!=0) return rec_dist[row][col];
    if (height[row][col]>=current_height) return 0;
    {
        int dist;
        dist = bfs(row-1, col, height[row][col]);
        rec_dist[row][col] = dist;
        dist = bfs(row+1, col, height[row][col]);
        rec_dist[row][col] = (dist>rec_dist[row][col]) ? dist : rec_dist[row][col];
        dist = bfs(row, col-1, height[row][col]);
        rec_dist[row][col] = (dist>rec_dist[row][col]) ? dist : rec_dist[row][col];
        dist = bfs(row, col+1, height[row][col]);
        rec_dist[row][col] = (dist>rec_dist[row][col]) ? dist : rec_dist[row][col];
    }
    rec_dist[row][col]++;
    return rec_dist[row][col];
}

int main() {
    cin>>r>>c;
    for (int i=0; i<r; i++) for (int j=0; j<c; j++) cin>>height[i][j];
    for (int i=0; i<r; i++) for (int j=0; j<c; j++)
        max_dist = (bfs(i, j, 2147483647)>max_dist) ? bfs(i, j, 2147483647) : max_dist;
    cout<<max_dist;
    return 0;

by Nicoppa @ 2019-09-12 15:55:56

嗯.. 这道题是记忆化搜索吧 我记得


by Wil_ @ 2019-09-17 13:20:37

需要用数组判重


|