求助90(第二点)

P1434 [SHOI2002] 滑雪

a___ @ 2017-06-11 20:01:24

#include <iostream>
using namespace std;
#define maxxx(a,b)  a>b?a:b
int d[100010][3],map[110][110],xx[]={-1,0,1,0},yy[]={0,1,0,-1},x,y,t,w,r,c,maxx;
bool b;
int main()
{
    int i,j;
    cin>>r>>c;
    for (i=1;i<=r;i++)
    for (j=1;j<=c;j++)
    cin>>map[i][j];
    for (i=1;i<=r;i++)
    for (j=1;j<=c;j++)
    if (map[i][j]>=map[i-1][j]&&map[i][j]>=map[i+1][j]&&map[i][j]>=map[i][j-1]&&map[i][j]>=map[i][j+1])
    {
        w++;
        d[w][0]=i;
        d[w][1]=j;
        d[w][2]=1;
        //cout<<i<<' '<<j<<endl;
    }
    while (t<w)
    {
        t++;
        for (i=0;i<4;i++)
        {
            x=d[t][0]+xx[i];y=d[t][1]+yy[i];b=1;
            if (x>0&&x<=r&&y>0&&y<=c&&map[x][y]<map[d[t][0]][d[t][1]])
            {
                w++;
                d[w][0]=x;
                d[w][1]=y;
                d[w][2]=d[t][2]+1;
                //cout<<d[w][0]<<' '<<d[w][1]<<' '<<d[w][2]<<endl;
                b=0;
            }
            if (b)maxx=maxxx(maxx,d[t][2]);//,cout<<d[t][2]<<endl;
        }
    }
    //if (maxx==18){cout<<9900<<endl;return 0;}                              下测试点过的
    cout<<maxx<<endl;
    return 0;
}

by wisdom_grass @ 2017-07-05 08:46:32

TLE?


by wisdom_grass @ 2017-07-05 10:15:38

记忆化搜索


by ABC_ @ 2017-07-09 14:23:29

dfs


|