NowCoder喜欢滑雪，因为滑雪的确很刺激。为了获得速度，必须从高处往低处滑。现在知道某片区域的海拔，如下所示
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。当然25-24-23-...-3-2-1是最长的一条。
现在给出区域的海拔，你能帮忙计算最长的滑道有多长吗？
[编程题]滑雪
- 热度指数：1206 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入包含多组数据。
每组数据的第一行包含两个正整数m和n (1≤m, n≤100)，紧接着是m*n的海拔矩阵，包含各个点的高度h (1≤h≤10000)。
输出描述:
对应每一组数据，输出该区域最长的滑道长度。
示例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 2 2 1 1 1 1
输出
25 1
Python BFS
# Python BFS def bfs(i,j,k): # 若存在记录，直接返回结果，节省时间 if i>=0 and i<R and j>=0 and j<C and A[i][j]<k and dis[i][j]>0: return dis[i][j] # 在不越界的情况下，寻找周围比自身小的结点的最长路径 elif i>=0 and i<R and j>=0 and j<C and A[i][j]<k: l=bfs(i,j-1,A[i][j]) u=bfs(i-1,j,A[i][j]) r=bfs(i,j+1,A[i][j]) d=bfs(i+1,j,A[i][j]) dis[i][j]=1+max(l,u,r,d) return dis[i][j] # 搜到底无路可走了 else: return 0 while True: try: R,C=map(int,input().split()) # 输入高和宽（行和列） A=[[] for i in range(R)] for i in range(R): A[i]=[int(n) for n in input().split()] #输入矩阵 dis=[[0 for i in range(C)] for j in range(R)] #作为顶点的最长路径 Max=0 for i in range(R): for j in range(C): dis[i][j]=bfs(i,j,A[i][j]+1) # 做记录 if Max<dis[i][j]: Max=dis[i][j] # 找到更长路径则更新Max print(Max) except EOFError: break
编辑于 2021-04-10 15:14:31
回复(0)
其实用到了动态规划的思想，需要保存计算出来的点的长度，避免重复计算。
// write your code here cpp
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100
int temp[MAX][MAX]; //定义一个二维数组，用来存放从终端输入的矩阵型数据
int maxsum[MAX][MAX];//用来存放已经计算出来的最长长度，初始化时都赋值为-1，表示该点没有计算过最长长度。
int row,col;//表示输入的行号和列号
int CalMaxLen(int r, int c)
{
if(maxsum[r][c]!=-1)
return maxsum[r][c];
int maxup, maxdown, maxleft, maxright;
if(r-1>=0 && temp[r][c]>temp[r-1][c])
maxup = CalMaxLen(r-1, c) + 1;
else
maxup = 1;
if(r+1<row && temp[r][c]>temp[r+1][c])
maxdown = CalMaxLen(r+1, c) + 1;
else
maxdown = 1;
if(c-1>=0 && temp[r][c]>temp[r][c-1])
maxleft = CalMaxLen(r, c-1) + 1;
else
maxleft = 1;
if(c+1<col && temp[r][c]>temp[r][c+1])
maxright = CalMaxLen(r, c+1) + 1;
else
maxright = 1;
int max1 = max(maxup, maxdown);
int max2 = max(maxleft, maxright);
int max3 = max(max1, max2);
maxsum[r][c] = max3;
return max3;
}
int main(int argc, char *argv[])
{
while(cin >> row >> col)
{
//进行终端输入和maxsum数组初始化为-1
for(int i=0; i<row; i++)
for(int j=0; j<col; j++){
cin>>temp[i][j];
maxsum[i][j] = -1;
}
int maxval = 0;
//计算每个点的最长长度
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
//打印最最长的点所在的长度
maxval = max(CalMaxLen(i, j), maxval);
}
}
cout << maxval << endl;
}
return 0;
}
发表于 2018-05-10 17:33:08
回复(0)
找出每一个局部最小点；从改点找所有能到的最高点并更新最长滑行距离，最后找出最大值。 #include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
#define INF 1000000
using namespace std;
bool checkMinimum(vector<vector<int>>& hills, int i, int j)
{
int m = hills.size(), n = hills[0].size();
if (i > 0 && hills[i - 1][j] < hills[i][j]) return false;
if (i < m - 1 && hills[i + 1][j] < hills[i][j]) return false;
if (j > 0 && hills[i][j - 1] < hills[i][j]) return false;
if (j < n - 1 && hills[i][j + 1] < hills[i][j]) return false;
return true;
}
void update(vector<vector<int>>& hills, vector<vector<int>>& dp, int i, int j,int val)
{
dp[i][j] = max(dp[i][j], val);
int m = hills.size(), n = hills[0].size();
++val;
if (i > 0 && hills[i - 1][j] > hills[i][j]) update(hills, dp, i - 1, j, val);
if (i < m - 1 && hills[i + 1][j] > hills[i][j]) update(hills, dp, i + 1, j, val);
if (j > 0 && hills[i][j - 1] > hills[i][j]) update(hills, dp, i, j - 1, val);
if (j < n - 1 && hills[i][j + 1] > hills[i][j]) update(hills, dp, i, j + 1, val);
}
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int m, n;
while (cin >> m >> n && m > 0 && n > 0)
{
vector<vector<int>> hills(m, vector<int>(n)), dp(m, vector<int>(n,-INF));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
cin >> hills[i][j];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (checkMinimum(hills, i, j))
{
update(hills, dp, i, j, 1);
}
int maxLen = 1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
maxLen = max(maxLen, dp[i][j]);
cout << maxLen << endl; }
return 0; }
编辑于 2017-07-18 16:24:36
回复(1)
首先采用遍历方式，根据题意求最长，自然采用深度优先搜索。
这里运用递归实现深度优先搜索。
但是需要面临一个问题就是时间复杂度，这里开辟一个二维数组保存当前点的最大滑下距离。
这样的优点就是：
当前点最大滑下距离只计算一次。计算其他点递归到改点时直接采用该点的值而不需再递归下去。
#include<cstdio>
int M, N;
int DIR[4][2] = { 0, 1, 0, -1, -1, 0, 1, 0 };
struct node
{
int height;
int value;
};
struct node MAP[100][100];
int FindMaxLength(int upLimit, int x, int y)
{
if (x < 0 || x >= M || y < 0 || y >= N) return 0;
if (MAP[x][y].height >= upLimit) return 0;
if (MAP[x][y].value != 0) return MAP[x][y].value;
int max = 0;
for (int i = 0; i < 4; i++){
int value = FindMaxLength(MAP[x][y].height, x + DIR[i][0], y + DIR[i][1]);
if (value > max) max = value;
}
MAP[x][y].value = max + 1;
return MAP[x][y].value;
}
int main()
{
while (scanf("%d%d",&M, &N) != EOF){
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
scanf("%d", &MAP[i][j].height);
MAP[i][j].value = 0;
}
}
int max = 0;
for (int i = 0; i < M; i++){
for (int j = 0; j < N; j++){
int value = FindMaxLength(MAP[i][j].height + 1, i, j);
if (value>max) max = value;
}
}
printf("%d\n", max);
}
return 0;
}
编辑于 2015-10-26 20:59:00
回复(0)
import java.util.*;
public class Main{
private static int[][] arr;
private static int[][] value;
private static int c;
private static int r;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
r = sc.nextInt();
c = sc.nextInt();
int max = 0;
arr = new int[r][c];
value = new int[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
arr[i][j] = sc.nextInt();
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
int temp = ski(i, j, Integer.MAX_VALUE);
if (temp > max) {
max = temp;
}
}
}
System.out.println(max);
}
sc.close();
}
/**
* @param c
* @param r
* @param maxValue
* @return
*/
private static int ski(int row, int col, int maxValue) {
if (col >= c || col < 0 || row >= r || row < 0 || maxValue <= arr[row][col] ) {
return 0;
}
if (value[row][col] > 0) {
return value[row][col];
}
value[row][col] = max(ski(row-1, col, arr[row][col]), ski(row+1, col, arr[row][col]), ski(row, col-1, arr[row][col]), ski(row, col+1, arr[row][col])) + 1;
return value[row][col];
}
/**
* @param ski
* @param ski2
* @param ski3
* @param ski4
* @return
*/
private static int max(int ski1, int ski2, int ski3, int ski4) {
// TODO Auto-generated method stub
return Math.max(Math.max(ski1, ski2), Math.max(ski3, ski4));
}
}
发表于 2016-04-13 11:57:48
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define INT_MAX 2147483647
struct dotline
{
int x;
int y;
int height;
dotline(int a, int b, int c){ x = a; y = b; height = c; }
};
int main()
{
int m, n;
while (cin>>m>>n)
{
vector<vector<int>> dp(m+2, vector<int>(n+2, 0));
vector<vector<int>> peek(m+2, vector<int>(n+2, INT_MAX));
vector<dotline> dot;
for (size_t i = 1; i <=m; i++)
{
for (size_t j = 1; j <=n; j++)
{
cin >> peek[i][j];
dotline tmp(i,j,peek[i][j]);
dot.push_back(tmp);
}
}
sort(dot.begin(), dot.end(), [=](dotline a, dotline b){return b.height > a.height; });
int maxLen = 0;
for (int i = 0; i < dot.size(); i++)
{
dotline tmp = dot[i];
if (peek[tmp.x][tmp.y]>peek[tmp.x][tmp.y + 1])
dp[tmp.x][tmp.y] = max(dp[tmp.x][tmp.y], dp[tmp.x][tmp.y + 1] + 1);
if (peek[tmp.x][tmp.y]>peek[tmp.x][tmp.y -1])
dp[tmp.x][tmp.y] = max(dp[tmp.x][tmp.y], dp[tmp.x][tmp.y - 1] + 1);
if (peek[tmp.x][tmp.y]>peek[tmp.x-1][tmp.y ])
dp[tmp.x][tmp.y] = max(dp[tmp.x][tmp.y], dp[tmp.x-1][tmp.y] + 1);
if (peek[tmp.x][tmp.y]>peek[tmp.x+1][tmp.y ])
dp[tmp.x][tmp.y] = max(dp[tmp.x][tmp.y], dp[tmp.x+1][tmp.y] + 1);
maxLen = max(maxLen, dp[tmp.x][tmp.y]);
}
cout << maxLen+1 << endl;
}
return 0;
}
发表于 2016-09-03 14:16:24
回复(0)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int m,n;
while(cin >> m >> n){
vector<vector<int>> area(m,vector<int> (n,0));
vector<vector<int>> cost(m,vector<int> (n,1));
vector<vector<int>> order(m*n,vector<int> (3,0));
int index=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
cin >> area[i][j];
order[index][0]= area[i][j];
order[index][1]= i;
order[index][2]= j;
index++;
}
}
//人人为我式 递推
sort(order.begin(),order.end());
int ans = 0;
int x,y;
for(int i=0;i<order.size();++i){
x = order[i][1];
y = order[i][2];
int maxlen = cost[x][y];
if(x-1>=0 && area[x-1][y] < area[x][y]){
maxlen = max(maxlen,cost[x-1][y]+1);
}
if(x+1<m && area[x+1][y] < area[x][y]){
maxlen = max(maxlen,cost[x+1][y]+1);
}
if(y-1>=0 && area[x][y-1] < area[x][y]){
maxlen = max(maxlen,cost[x][y-1]+1);
}
if(y+1<n && area[x][y+1] < area[x][y]){
maxlen = max(maxlen,cost[x][y+1]+1);
}
cost[x][y] = maxlen;
ans = max(cost[x][y],ans);
}
cout << ans << endl;
}
return 0;
}
发表于 2022-01-26 14:08:56
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int put[100][100];
int dp[100][100];
void dfs(int rows,int cols,int row, int col)
{
vector<int> tmp;
if(row+1<rows && put[row][col] > put[row+1][col]) //右边
{
if(dp[row+1][col] == 0)
dfs(rows,cols,row+1,col);
tmp.push_back(dp[row+1][col]);
}
if(row-1>=0 && put[row][col] > put[row-1][col]) //左边
{
if(dp[row-1][col] == 0)
dfs(rows,cols,row-1,col);
tmp.push_back(dp[row-1][col]);
}
if(col+1<cols && put[row][col] > put[row][col+1]) //上
{
if(dp[row][col+1] == 0)
dfs(rows,cols,row,col+1);
tmp.push_back(dp[row][col+1]);
}
if(col-1>=0 && put[row][col] > put[row][col-1]) //下
{
if(dp[row][col-1] == 0)
dfs(rows,cols,row,col-1);
tmp.push_back(dp[row][col-1]);
}
if(tmp.size()==0) //周围无路可走
dp[row][col] =1;
else
dp[row][col] = *max_element(tmp.begin(),tmp.end()) + 1;
}
int main()
{
int m,n;
while(cin>>m>>n)
{
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
cin>>put[i][j]; //获得输入
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
dp[i][j]=0; //状态置0
int res =0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{ if(dp[i][j] == 0) //判断该点是否遍历计算过
dfs(m,n,i,j);
res = max(res,dp[i][j]);
}
cout<<res<<endl;
}
return 0;
}
编辑于 2019-08-30 16:04:38
回复(1)
/* 有保存的dfs方法
*/
#include<iostream>
#include<vector>
using namespace std;
int dfs(vector<vector<int>>&b,vector<vector<int> >&ans,int x,int y)
{
if(ans[x][y]!=-1)
return ans[x][y];
int m=b.size();
int n=b[0].size();
ans[x][y]=1; //核心，处理极小值情况，否则会死循环
if(x>0 && b[x][y]>b[x-1][y])
ans[x][y]=max(ans[x][y],dfs(b,ans,x-1,y)+1);
if(x<m-1 && b[x][y]>b[x+1][y])
ans[x][y]=max(ans[x][y],dfs(b,ans,x+1,y)+1);
if(y>0 && b[x][y]>b[x][y-1])
ans[x][y]=max(ans[x][y],dfs(b,ans,x,y-1)+1);
if(y<n-1 && b[x][y]>b[x][y+1])
ans[x][y]=max(ans[x][y],dfs(b,ans,x,y+1)+1);
return ans[x][y];
}
int main()
{
int m,n;
while(cin>>m>>n)
{
vector<vector<int> > b(m,vector<int>(n));
vector<vector<int> > ans(m,vector<int>(n,-1));
for(auto&x:b)
for(auto&y:x)
cin>>y;
int res=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
res=max(res,dfs(b,ans,i,j));
cout<<res<<endl;
}
return 0;
}
编辑于 2018-07-23 23:00:40
回复(0)
#include<stdio.h>
#include<string.h>
int r,c,max=0;
int a[101][101];
int ans[10020];
int book[101][101];
int next[4][2]={
-1,0,
1,0,
0,-1,
0,1
};
void dfs(int x,int y,int n)
{
// printf("%d %d\n",a[x][y],n);
int i,j,tx,ty;
if(n>max)
{
max=n;
}
if(x>=r||x<0||y>=c||y<0)
return ;
if(n>0&&a[x][y]>=ans[n-1])
return ;
book[x][y]=1;
ans[n]=a[x][y];
for(i=0;i<4;i++)
{
tx=x,ty=y;
tx+=next[i][0];
ty+=next[i][1];
if(book[tx][ty]==1)
continue;
else
{
dfs(tx,ty,n+1);
book[tx][ty]=0;
}
}
return ;
}
int main()
{
int i,j;
scanf("%d%d",&r,&c);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
scanf("%d",&a[i][j]);
// printf("%d ",a[i][j]);
}
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
dfs(i,j,0);
memset(book,0,sizeof(book));
}
printf("%d\n",max);
return 0;
}
#include<string.h>
int r,c,max=0;
int a[101][101];
int ans[10020];
int book[101][101];
int next[4][2]={
-1,0,
1,0,
0,-1,
0,1
};
void dfs(int x,int y,int n)
{
// printf("%d %d\n",a[x][y],n);
int i,j,tx,ty;
if(n>max)
{
max=n;
}
if(x>=r||x<0||y>=c||y<0)
return ;
if(n>0&&a[x][y]>=ans[n-1])
return ;
book[x][y]=1;
ans[n]=a[x][y];
for(i=0;i<4;i++)
{
tx=x,ty=y;
tx+=next[i][0];
ty+=next[i][1];
if(book[tx][ty]==1)
continue;
else
{
dfs(tx,ty,n+1);
book[tx][ty]=0;
}
}
return ;
}
int main()
{
int i,j;
scanf("%d%d",&r,&c);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
scanf("%d",&a[i][j]);
// printf("%d ",a[i][j]);
}
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
dfs(i,j,0);
memset(book,0,sizeof(book));
}
printf("%d\n",max);
return 0;
}
水过了？迷
发表于 2018-05-06 23:11:34
回复(0)
您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为21.43% 测试用例: 3 3 对应输出应该为: 4 你的输出为: 6 .. why.. // write your code here cpp #include<iostream> #include<vector> using namespace std; int recursive(int a, int b, vector<vector<int> > &all, vector<vector<int> > &all_out){ int h = all.size(); int w = all[0].size(); if(a < 0 || a >= h || b < 0 || b >= w) return 0; if(all_out[a][b] > 0) return all_out[a][b]; int max = 1; for(int i=-1; i<2; i+=2){ if(a+i >= 0 && a+i < h){ if(all[a+i][b] < all[a][b]){ int tt = 0; if(all_out[a+i][b] > 0) tt = all_out[a+i][b]; else tt = recursive(a+i, b, all, all_out); tt = tt + all[a][b] - all[a+i][b]; max = max > tt ? max : tt; } } } for(int j=-1; j<2; j+=2){ if(b+j >= 0 && b+j < w){ if(all[a][b+j] < all[a][b]){ int tt = 0; if(all_out[a][b+j] > 0) tt= all_out[a][b+j]; else tt = recursive(a, b+j, all, all_out); tt = tt + all[a][b] - all[a][b+j]; max = max > tt ? max : tt; } } } all_out[a][b] = max; return all_out[a][b]; } int main(){ int a, b; while(cin >> a >> b){ vector<vector<int> > all; vector<vector<int> > all_out; for(int i=0; i<a; ++i){ vector<int> temp(b, -1); vector<int> temp_out(b, -1); all.push_back(temp); all_out.push_back(temp_out); } for(int i=0; i<a; ++i) for(int j=0; j<b; ++j) cin >> all[i][j]; //int t = recursive(0, 0, all, all_out); int out = 0; for(int i=0; i<a; ++i) for(int j=0; j<b; ++j) int tt = recursive(i, j, all, all_out); for(int i=0; i<a; ++i) for(int j=0; j<b; ++j) out = out > all_out[i][j] ? out : all_out[i][j]; cout << out << endl; } }
发表于 2018-03-07 14:03:05
回复(0)
没懂为什么通不过。测试用例也没给全。
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为4.76%
测试用例:
16 17 18 19 6
对应输出应该为:
2
你的输出为:
1
#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[102][102];
int dfs(int i, int j) {
if (i < 1 || i > m || j < 1 || j > n)
return 0;
int left = 0, right = 0, up = 0, down = 0;
if (a[i][j] > a[i][j - 1])
left = dfs(i, j - 1) + 1;
if (a[i][j] > a[i - 1][j])
up = dfs(i - 1, j) + 1;
if (a[i][j] > a[i][j + 1])
right = dfs(i, j + 1) + 1;
if (a[i][j] > a[i + 1][j])
down = dfs(i + 1, j) + 1;
return max(left, max(up, max(right, down)));
}
int main(int argc, char const *argv[]) {
while (cin >> m >> n) {
int i, j, maxLen = 0;
memset(a, 0, sizeof(a));
for (i = 1; i <= m; ++i)
for (j = 1; j <= n; ++j)
cin >> a[i][j];
for (i = 1; i <= m; ++i)
for (j = 1; j <= n; ++j)
maxLen = max(maxLen, dfs(i, j));
printf("%d\n", maxLen);
}
return 0;
}
发表于 2018-03-02 12:23:58
回复(1)
// write your code here cpp
// nk.cpp : 定义控制台应用程序的入口点。
#include<iostream>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int m, n;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };
struct pre
{
int height;
int val;
};
vector<vector<pre>> result(100, vector<pre>(100));
int Find(int upLimit, int x, int y)
{
if (x < 0 || x >= m || y < 0 || y >= n) return 0;
if (result[x][y].height >= upLimit) return 0;
if (result[x][y].val != 0) return result[x][y].val;
int max = 0;
for (int i = 0; i < 4; i++) {
int value = Find(result[x][y].height, x + dir[i][0], y + dir[i][1]);
if (value > max) max = value;
}
result[x][y].val = max + 1;
return result[x][y].val;
}
int main()
{
int i, j;
while (cin >> m >> n)
{
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
cin >> result[i][j].height;
result[i][j].val = 0;
}
}
int max = 0,value;
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
value = Find(result[i][j].height+1, i, j);
if (max < value)
max = value;
}
}
cout << max<< endl;
}
return 0;
}
// nk.cpp : 定义控制台应用程序的入口点。
#include<iostream>
#include <vector>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
int m, n;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };
struct pre
{
int height;
int val;
};
vector<vector<pre>> result(100, vector<pre>(100));
int Find(int upLimit, int x, int y)
{
if (x < 0 || x >= m || y < 0 || y >= n) return 0;
if (result[x][y].height >= upLimit) return 0;
if (result[x][y].val != 0) return result[x][y].val;
int max = 0;
for (int i = 0; i < 4; i++) {
int value = Find(result[x][y].height, x + dir[i][0], y + dir[i][1]);
if (value > max) max = value;
}
result[x][y].val = max + 1;
return result[x][y].val;
}
int main()
{
int i, j;
while (cin >> m >> n)
{
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
cin >> result[i][j].height;
result[i][j].val = 0;
}
}
int max = 0,value;
for (i = 0; i < m; ++i)
{
for (j = 0; j < n; ++j)
{
value = Find(result[i][j].height+1, i, j);
if (max < value)
max = value;
}
}
cout << max<< endl;
}
return 0;
}
发表于 2017-12-06 20:41:53
回复(0)
1、建立滑雪场。设MAX=10001，在滑雪场周围一圈建立“围墙”，即值都为MAX
2、输入滑雪场的数据
3、从低（1,1）到（m,n）位置开始循环，寻找从每个位置为起点的滑雪路径长度，并找出其中的最大值。
4.从第（i,j）点开始滑雪，初始路径长度num为1，并进行递归
1）如果d[i][j]小于四个方向的值说明已经走到头了，对num进行处理，return。
2）分别从上下左右四个方向进行递归，递归前要进行值的对比，并将num+1（只有要改方向的值小于d[i][j]才可以进行）
2、输入滑雪场的数据
3、从低（1,1）到（m,n）位置开始循环，寻找从每个位置为起点的滑雪路径长度，并找出其中的最大值。
4.从第（i,j）点开始滑雪，初始路径长度num为1，并进行递归
1）如果d[i][j]小于四个方向的值说明已经走到头了，对num进行处理，return。
2）分别从上下左右四个方向进行递归，递归前要进行值的对比，并将num+1（只有要改方向的值小于d[i][j]才可以进行）
#include<stdio.h>
#define MAX 10005
int max;
int m,n;
void compute(int d[][102],int x,int y,int num)
{
int t=d[x][y];
/**如果（i，j）点的值小于四个方向的值，说明已经到了终点，处理num，并return*/
if(t<=d[x-1][y]&&t<=d[x+1][y]&&t<=d[x][y-1]&&t<=d[x][y+1])
{
max=max>num?max:num;
return ;
}
/**沿四个方向开始递归*/
if(t>d[x-1][y])
compute(d,x-1,y,num+1);
if(t>d[x+1][y])
compute(d,x+1,y,num+1);
if(t>d[x][y-1])
compute(d,x,y-1,num+1);
if(t>d[x][y+1])
compute(d,x,y+1,num+1);
return ;
}
int main()
{
int i,j;
int d[102][102];
while(scanf("%d %d",&m,&n)!=EOF)
{
max=0; /**初始步数为0*/
for(i=0;i<102;i++) /**建立“围墙”*/
for(j=0;j<102;j++)
d[i][j]=MAX;
for(i=1;i<=m;i++) /**录入滑雪场的值*/
for(j=1;j<=n;j++)
scanf("%d",&d[i][j]);
for(i=1;i<=m;i++) /**从每个点开始滑雪*/
for(j=1;j<=n;j++)
{
compute(d,i,j,1);
}
printf("%d\n",max);
}
return 0;
}
发表于 2017-03-04 12:48:27
回复(0)
问题信息
难度：
14条回答
13收藏
24262浏览
通过挑战的用户
查看代码-
2023-01-05 20:45:25
-
2022-10-17 20:37:58 -
2022-09-22 19:17:29 -
2022-06-11 01:31:36
-
2022-05-11 22:20:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
