求助80!!!dfs

P1434 [SHOI2002] 滑雪

ko_no_lzx_da @ 2021-10-11 13:44:57

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int a[1000][1000],book[1000][1000];
int xx[4]={0,0,-1,1};
int yy[4]={1,-1,0,0};
int maxx,maxy,mmax,r,c;
int maax=-1;
void dfs(int idx,int idy){
    int k=0;
    for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(book[i][j]==1){
                    k++;
                }
            }
        }
    if(k>maax){
        maax=k;
    }
    for(int i=0;i<4;i++){
        int dx=idx+xx[i];
        int dy=idy+yy[i];
        if(dx>=r||dx<0||dy<0||dy>=c)continue;
        if(book[dx][dy]==0&&a[dx][dy]<a[idx][idy]){
            book[dx][dy]=1;
            dfs(dx,dy);
            book[dx][dy]=0;
        }
    }
} 
int main(){
    cin >>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >>a[i][j];
            if(a[i][j]>mmax){
                mmax=a[i][j];
                maxx=i;
                maxy=j;
            }
        }
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            book[i][j]=1;
            dfs(i,j);
            book[i][j]=0;
        }
    }
    cout <<maax;
    return 0;
}

by 绫韵华音 @ 2021-10-11 14:35:48

是T了还是WA了 如果是T了试试记忆化搜索什么的~


by Aa0815 @ 2021-10-20 17:44:25

确实是T了,楼上正解


by Nephren_Sakura @ 2021-10-22 08:39:01

@ko_no_lzx_da

需要记忆化


|