|
# [SHOI2002] 滑雪
## 题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
```
1?? 2?? 3?? 4?? 5
16? 17? 18? 19? 6
15? 24? 25? 20? 7
14? 23? 22? 21? 8
13? 12? 11? 10? 9
```
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24$－$17$－$16$－$1$（从 $24$ 开始，在 $1$ 结束）。当然??? $25$－$24$－$23$－$\ldots$－$3$－$2$－$1$ 更长。事实上，这是最长的一条。
## 输入格式
输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行，每行有 $C$ 个数，代表高度(两个数字之间用 $1$ 个空格间隔)。
## 输出格式
输出区域中最长滑坡的长度。
## 样例 #1
### 样例输入 #1
```
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
```
### 样例输出 #1
```
25
```
## 提示
对于 $100\%$ 的数据，$1\leq R,C\leq 100$。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define bug cout << "---------------------" << endl
using namespace std;
constexpr int N = 300;
int res=-1;
int mp[N][N];
int dp[N][N]={1};
bool vis[N][N];
int n, m;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool in(int x, int y) {
return x >= 0 && x < n&& y >= 0 && y < m;
}
int dfs(int x,int y) {
if (vis[x][y]) {
return dp[x][y];
}
vis[x][y] = true;
for (int i = 0;i < 4;i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && mp[tx][ty] < mp[x][y]) {
dp[x][y] = max(dp[x][y],dfs(tx,ty)+1);
}
}
return dp[x][y];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> mp[i][j];
}
}
memset(vis, false, sizeof(vis));
res = -1;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
res = max(res, dfs(i, j));
}
}
cout << res << endl;
}
第二份代码通过初始化dp数组为-1是否访问过，而且需要注意，如果该点无法走任意的路需要让其为1
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define bug cout << "---------------------" << endl
using namespace std;
constexpr int N = 300;
int res=-1;
int mp[N][N];
int dp[N][N]={1};
int n, m;
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool in(int x, int y) {
return x >= 0 && x < n&& y >= 0 && y < m;
}
int dfs(int x,int y) {
if (dp[x][y]!=-1) {
return dp[x][y];
}
dp[x][y] = 1;
for (int i = 0;i < 4;i++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if (in(tx, ty) && mp[tx][ty] < mp[x][y]) {
dp[x][y] = max(dp[x][y],dfs(tx,ty)+1);
}
}
return dp[x][y];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> mp[i][j];
}
}
res = -1;
memset(dp, -1, sizeof(dp));
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
res = max(res, dfs(i, j));
}
}
cout << res << endl;
}
第三份宽搜代码：实现方式与DFS几乎类似；
不同之处在于进行了顺序优化，将所有的可能性，以结构体存入队列进行依次访问！
#include <queue>//队列的头文件
#include <cstdio>
#include <iostream>//我写代码都是直接吧这两个头文件直接写上去的不管用没有用
#include <algorithm>//我不想写一个max函数了
using namespace std;
struct Good //对于b数组和队列q i和j都是储存该点的坐，对于数组b来说 num储存的是该座标的值队列q储存的是该坐标元素是从前到后第几个元素
{
int i;
int j;
int num;
}b[10010];
int a[110][110];//正确的储存读入的二维数组
bool cmp(const Good& a, const Good& b)
{
return a.num > b.num;//使该结构体如果要排序的话按照降序方式排序
}
const int lj[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };//上右下左的顺序
int main()
{
queue<Good>q;//定义一个队列
int qs = 0;//储存b数组的元素好像可以用其他代数式代替，不过无所谓了
int n, m;
cin >> n >> m;
for (int i = 1;i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];//正确的读入
b[qs].i = i;//按顺序读入到一维数组中
b[qs].j = j;
b[qs++].num = a[i][j];
}
int ans = -1;//先初始化最长的长度为-1
sort(b, b + qs, cmp);//排序b数组
for (int i = 0; i < qs / 2 + 1; i++)//这里的qs/2是一个玄学优化，不过洛谷上好像没有数据能卡这个
{
q.push({ b[i].i,b[i].j,1 });//先找最大的一个元素入列，后面的元素依次入列
while (!q.empty())//如果队列不为空
{
Good qa = q.front();//取出队首元素
q.pop();
ans = max(qa.num, ans);//判断长度
for (int j = 0;j < 4; j++)
{
int x = qa.i + lj[j][0];//往四个方向依次查找
int y = qa.j + lj[j][1];
if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] < a[qa.i][qa.j])//如果这个数没有出界，并且严格小于上一个元素就入列
{
q.push({ x,y,qa.num + 1 });
}
}
}
}
cout << ans << endl;//输出最大长度
return 0;
}
|