70 分 求助

P1434 [SHOI2002] 滑雪

maxiantao2059 @ 2019-03-19 18:00:57

include<iostream>

include<algorithm>

using namespace std; int f[101][101],dir[4][2]={1,0,-1,0,0,1,0,-1}; int c,r,map[101][101]; int t,maxn,sx,sy; struct node { int x,y,r; }tmp[100001];

int dfs(int x,int y) { if(x==sx&&y==sy) return 1; if( f[x][y]!=0 ) return f[x][y];

for(int i=0;i<=3;i++)
{
    int xx=x+dir[i][0];
    int yy=y+dir[i][1];
    if( xx>0&&xx<=r&&yy>0&&yy<=c&&map[x][y]>map[xx][yy] )
    {
        //cout<<xx<<" "<<yy<<endl;
        f[x][y] = max ( dfs(xx,yy)+1 , f[x][y] );

     } 
}

return f[x][y];

}

int cmp(node x,node y) { return x.r<y.r; } int main() { t=1; cin>>r>>c; for(int i=1;i<=r;i++) { for(int j=1;j<=c;j++) { //cout<<t<<endl; cin>>map[i][j]; tmp[t].x=i; tmp[t].y=j; tmp[t].r=map[i][j]; t++; } } sort(tmp+1,tmp+t,cmp); sx=tmp[1].x; sy=tmp[1].y; //cout<<sx<<sy<<endl;kp / for(int i=1;i<t;i++) { cout<<tmp[i].x<<" "<<tmp[i].y<<" "<<tmp[i].r<<endl; } /

for(int i=1;i<t;i++)
{
    f[tmp[i].x][tmp[i].y] = dfs( tmp[i].x , tmp[i].y );
    /*
    cout<<endl;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
    */
        maxn = max( maxn , f[tmp[i].x][tmp[i].y] );

        //cout<<"maxn="<<maxn<<endl;
  }
//dfs(2,5);
/*
cout<<endl;
for(int i=1;i<=r;i++)
{
    for(int j=1;j<=c;j++)
    {
        cout<<f[i][j]<<" ";
    }
    cout<<endl;
}
*/
cout<<maxn<<endl;

return 0;

}


by 澪lane @ 2019-03-19 18:11:44

希望更丰富的展现?使用Markdown

by 2017gdgzoi999 @ 2019-03-19 18:27:33

希望更丰富的展现?使用Markdown


by Smile_Cindy @ 2019-03-19 18:28:07

希望更丰富的展现?使用Markdown


by 2017gdgzoi999 @ 2019-03-19 18:30:20

希望更丰富的展现?使用Markdown


by ZhuMingYang @ 2019-03-19 19:29:14

\small{u^se\ \ \ \ l^at^ex}

|