pts80, WA on #1 #10, 求调

SingKwenCat @ 2024-10-12 17:45:39

#include <iostream>
#include <algorithm>

#define IOS std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define endl "\n"

using namespace std;

constexpr const int N = 105;

long long a[N][N], mem[N][N], vis[N][N];
long long n, m, minx, miny, mini = 0x3f3f3f3f3f3f;

long long dfs(int x, int y) {
  if (mem[x][y]) return mem[x][y];
  if (vis[x][y]) return -1;
  vis[x][y] = 1;
  long long ans = 0;
  if (x-1>=0 && a[x-1][y] > a[x][y]) ans = max(ans, dfs(x-1, y));
  if (x+1< n && a[x+1][y] > a[x][y]) ans = max(ans, dfs(x+1, y));
  if (y-1>=0 && a[x][y-1] > a[x][y]) ans = max(ans, dfs(x, y-1));
  if (y+1< m && a[x][y+1] > a[x][y]) ans = max(ans, dfs(x, y+1));
  ans += 1;
  mem[x][y] = ans, vis[x][y] = 0;
  return ans;
}

int main() {
  IOS
  cin >> n >> m;
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
      if (a[i][j] < mini) mini = a[i][j], minx = i, miny = j;
  }
  cout << dfs(minx, miny) << endl;
  return 0;
}

by ccch1ennn @ 2024-10-12 18:42:16

嘶...好像不能直接从最低点往上搜吧

by ccch1ennn @ 2024-10-12 18:47:17

#include <iostream>
#include <algorithm>

#define IOS std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define endl "\n"

using namespace std;

constexpr const int N = 105;

long long a[N][N], mem[N][N], vis[N][N];
long long n, m, minx, miny, mini = 0x3f3f3f3f3f3f,kkk=0;

long long dfs(int x, int y) {
  if (mem[x][y]) return mem[x][y];
  if (vis[x][y]) return -1;
  vis[x][y] = 1;
  long long ans = 0;
  if (x-1>=0 && a[x-1][y] > a[x][y]) ans = max(ans, dfs(x-1, y));
  if (x+1< n && a[x+1][y] > a[x][y]) ans = max(ans, dfs(x+1, y));
  if (y-1>=0 && a[x][y-1] > a[x][y]) ans = max(ans, dfs(x, y-1));
  if (y+1< m && a[x][y+1] > a[x][y]) ans = max(ans, dfs(x, y+1));
  ans += 1;
  mem[x][y] = ans, vis[x][y] = 0;
  return ans;
}

int main() {
  IOS
  cin >> n >> m;
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
      cin >> a[i][j];     
  }
  for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
      kkk=max(kkk,dfs(i,j));
  }
  cout << kkk << endl;
  return 0;
}

万一是

1 7 2
8 9 3
6 5 4

这种不就从1被卡了

by SingKwenCat @ 2024-10-12 22:35:26

@ccch1ennn 呜啊，谢谢大佬，我去改一下