#2TLE求解

P1434 [SHOI2002] 滑雪

Kanoshuuya @ 2019-08-01 15:28:13

#include <bits/stdc++.h>

using namespace std;

struct point{
    int x,y;
    int val;
    int step;
}p[101][101];

int r,c;
int dx[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
int Max = -1;

int isOK(int x,int y){
    if(x>=0&&x<r&&y>=0&&y<c)    return 1;
    else                        return -1;
}

void bfs(int x,int y){
    queue<point> q;
    q.push(p[x][y]);
    while(q.size()>0){
        point n = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx = n.x+dx[i][0];
            int yy = n.y+dx[i][1];
            if(p[xx][yy].val<n.val&&isOK(xx,yy)==1){
                p[xx][yy].step = max(n.step + 1,p[xx][yy].step);
                Max = max(p[xx][yy].step,Max);
                q.push(p[xx][yy]);
            }
        }
    }
}

int main()
{
    cin>>r>>c;
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++){
            cin>>p[i][j].val;
            p[i][j].x = i;
            p[i][j].y = j;
            p[i][j].step = 1;
        }
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++){
            if(p[i][j].step==1)
                bfs(i,j);
        }
    if(Max>0)
        cout<<Max<<endl;
    else
        cout<<1;
    return 0;
}

用的是BFS,不知道还有没有救


by Lacrymabri @ 2019-08-03 17:18:59

开o2优化就能过了(我也不知道为什么,可能stl的模板类比较慢吧)


by Neptune0 @ 2019-08-04 18:38:20

我觉得楼主这个暴搜不行是因为

这是个暴搜嘛 建议用记忆化深搜。


by Kanoshuuya @ 2019-08-05 15:30:35

@Lacrymabri 开了o2依然TLE 可能还是得用DFS剪枝吧


by Kanoshuuya @ 2019-08-05 15:31:40

@Neptune0 一开始用了BFS不想改DFS 我去试试


by Lacrymabri @ 2019-08-09 15:09:42

@Kanoshuuya 我也用的是bfs,也是第二组TLE,加了o2就过了(逃)


|