题目
给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
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−2−1。
在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 R 和 C。
接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤300,
0≤矩阵中整数≤10000
输入样例：
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
输出样例：
25
模板
int g[MAXN];
int dp(状态参数) {
if (g[规模] != 无效数值) return g[规模];
if (终止条件) return 最小子问题解;
g[规模] = f(缩小规模);
return g[规模];
}
int main() {
// ...
memset(g, 无效数值, sizeof(g));
// ...
}
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 310;
int n,m;
int h[N][N];
int f[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dp(int x,int y)
{
int &v=f[x][y];
if(v!=-1) return v;
v=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&h[x][y]>h[a][b])
v=max(v,dp(a,b)+1);
}
return v;
}
int main()
{
scanf("%d%d", &n, &m);
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d", &h[i][j]);
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
res=max(res,dp(i,j));
}
printf("%d\n",res);
return 0;
}
类似题目
给定一个 n×m 的方格矩阵。
每个方格中都包含一个大写字母：Q,W,E,R 之一。
现在，小明要在方格矩阵中进行移动。
具体移动规则如下：
1.最初，小明应选择某个包含字母 Q 的方格作为起点。
2.小明每次移动可以沿上下左右四个方向，移动一格距离。当然不能出界。
3.小明在移动时，必须遵循：从包含字母 Q 的方格只能移动到包含字母 W 的方格，从包含字母 W 的方格只能移动到包含字母 E 的方格，从包含字母 E 的方格只能移动到包含字母 R 的方格，从包含字母 R 的方格只能移动到包含字母 Q 的方格。
4.小明每走过一个完整的 QWER，就称小明走过了一个轮次。小明需要走过尽可能多的轮次。即统计路径中完整的QWER的个数，例如WERQWERQ中仅有1个个QWER。
请问小明最多可以走过多少轮次？
输入格式
第一行包含两个整数 n,m。
接下来 n 行，每行包含 m 个字符，每个字符为 Q,W,E,R 之一。
输出格式
如果小明无法成功走过任何轮次，则输出 none。
如果小明可以成功走过无穷多轮次，则输出 infinity。
如果小明可以成功走过有限多轮次，则输出他能走过的最多轮次。
数据范围
前六个测试点满足 1≤n,m≤5。
所有测试点满足 1≤n,m≤1000。
输入样例1：
1 2
QW
输出样例1：
none
输入样例2：
2 2
ER
WQ
输出样例2：
infinity
输入样例3：
5 5
QWERQ
QWERW
QWERE
QQERR
RREWQ
输出样例3：
4
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1010;
char g[N][N];
int f[N][N];
bool st[N][N];
bool flag;
int n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x,int y)
{
if(flag) return -1;
int& v=f[x][y];
if(v!=-1) return v;
st[x][y]=true;
v=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]==(g[x][y]+1)%4)
{
if(st[a][b])
{
flag=true;
return -1;
}
v=max(v,dp(a,b)+1);
}
}
st[x][y]=false;
return v;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
{
scanf("%s",g[i]);
for(int j=0;j<m;j++)
{
char& c=g[i][j];
if(c=='Q') c=0;
else if(c=='W') c=1;
else if(c=='E') c=2;
else c=3;
}
}
int res=0;
memset(f,-1,sizeof f);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int t=dp(i,j);
if(g[i][j]) t-=4-g[i][j];
res=max(res,t/4);
}
if(flag) puts("infinity");
else if(!res) puts("none");
else printf("%d\n",res);
return 0;
}
