80分代码求助

P1434 [SHOI2002] 滑雪

bengyy @ 2022-08-26 08:33:40

//1434 滑雪
#include <bits/stdc++.h>
using namespace std;
int R, C;
int m[110][110], s[110][110], vis[110][110], stotal, depth[1001000];
int mx[4] = {0,1,0,-1}, my[4] = {1,0,-1,0};//right down left up

struct Startpoint {
    int y, x;
}st[10010], q[10010];

void findstart(int x, int y){//actually it is a dfs判断每一个点是否可以成为出发点,只有比周围点都高才可能成为出发点
    if (y == 0 || x == 0 || y == R+1 || x == C+1) {s[y][x] = -1; return;}
    if (vis[y][x] == 1) {return;}
    for (int i = 0; i <= 3; i++) {
        int cmpx = x+mx[i], cmpy = y+my[i];
        if (cmpx >= 1 && cmpy >= 1 && cmpx <= R && cmpy <= C) {
            if (m[cmpy][cmpx] < m[y][x]) {s[cmpy][cmpx] = 1;}//0 means 'is a start'  1 means 'not a start'
            else if (m[cmpy][cmpx] > m[y][x]) {s[y][x] = 1;}
            vis[y][x] = 1;
            findstart(cmpx, cmpy);
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> m[j][i];//m[y][x]
        }
    }
    findstart(R/2, C/2);
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (s[j][i] == 0) {st[stotal++] = {j,i};}
        }
    }
    int maxlength = 1;
    for (int i = 0; i < stotal; i++) {
        //cout << st[i].x << ' ' << st[i].y << endl;
        int l = 1, r = 1;
        depth[1] = 1;
        q[1] = st[i];
        while (l <= r) {//广度优先搜索 以depth确定步数
            for (int j = 0; j < 4; j++) {
                int fx = q[l].x+mx[j];
                int fy = q[l].y+my[j];
                if (m[fy][fx] < m[q[l].y][q[l].x] && fy >= 1 && fx >= 1 && fy <= C && fx <= R) {
                    r++;
                    q[r].x = fx, q[r].y = fy;
                    depth[r] = depth[l] + 1;
                    //cout << q[r].x << ' ' << q[r].y << endl;
                }
            }
            l++;
        }
        maxlength = (maxlength >= depth[r] ? maxlength: depth[r]);
    }
    cout << maxlength;
    return 0;
}

有RE 错误是内存溢出 有一个WA


by Jim777 @ 2022-08-26 09:25:38

@[bengyy](/user/750955) 
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ma=0;
int a[101][101],s[101][101],mx;
bool f[101][101];
int fxszx[]={0,0,1,-1};
int fxszy[]={1,-1,0,0};
int dfs(int dx,int dy)
{
  if(s[dx][dy])
  {
    return s[dx][dy];
  }
  s[dx][dy]=1;
  for(int i=0;i<4;i++)
  {
    int x=dx+fxszx[i];
    int y=dy+fxszy[i];
    if(x<1||y>m||x>n||y<1)continue;
    if(a[x][y]>a[dx][dy])
    {
        dfs(x,y);
        s[dx][dy]=max(s[dx][dy],s[x][y]+1);
    }
  }
  return s[dx][dy];
}
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
      scanf("%d",&a[i][j]);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      mx=max(mx,dfs(i,j));
    }
  cout<<mx;
  return 0;
}

by bengyy @ 2022-08-26 09:55:34

@Jim777 深搜会不会超时啊,我用广搜总是有一两个WA


by LYM20114 @ 2022-08-27 21:21:04

这是记忆化搜索诶兄弟


by LYM20114 @ 2022-08-27 21:21:26

广搜会TLE


by bengyy @ 2022-09-07 10:51:21

@LYM2011 是我菜了,不熟练(虽然但是,优化后的广搜不会TLE)


|