题目描述:
输出格式
输出一个整数,表示可完成的最长滑雪长度。
数据范围
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
usingnamespacestd; constintN=310; intf[N][N]; //状态数组,表示从i,j开始滑能滑倒的所有距离中的最大值inth[N][N]; //滑雪场intn,m; intst[N][N]; //该点是否搜索到intdx[4] = {-1, 1, 0, 0}; intdy[4] = {0, 0, -1, 1}; intdfs(intx, inty) { //已经搜索了,直接返回f[x][y]这个最大值if (st[x][y]) returnf[x][y]; //否则置为该点已经搜索st[x][y] =1; f[x][y] =1; //自己这个点就是一步 for (inti=0; i<4; i++) { intnx=x+dx[i];intny=y+dy[i]; if (nx<1||nx>n||ny<1||ny>m) continue; if (h[nx][ny] >=h[x][y]) continue; f[x][y] =max(f[x][y],dfs(nx,ny) +1); } returnf[x][y]; } intmain() { cin>>n>>m; for (inti=1; i<=n; i++) for (intj=1; j<=m; j++) cin>>h[i][j]; intres=0; //暴搜所有点如果一次可以到所有点根本一次搜索即可//这道题可以看成一个非联通图 从一个点无所搜到所有点,只能搜到部分点,搜到的部分点一定是最大值//因为 从1个点开始上下左右走的所有路径都是固定的,在第一此搜索中就会把从f[1][1]能搜到的所有点的f[i][j]都找出来//因为路径是固定的,所以搜过的点不需要在 重复搜索for (inti=1; i<=n; i++) for (intj=1; j<=m; j++) res=max(res,dfs(i,j)); cout<<res; }