SSL P2434 取数

SSL P2434 取数

目录：

• 题目：
• 分析：
• 思路：
• 代码：

题目：

取数 题目

分析：

对于这道题目，我们理应想到的是记搜，但小编的同学竟然用暴搜AC了！！！所以小编这里就发下暴搜吧

思路：

1.枚举从哪个点开始
2.dfs求出最优解

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
inline LL read() {LL d=0,f=1;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}return d*f;
}
int n,m,a[111][111],b[10011],maxn,t;
void dfs(int x,int y,int k,int o) 
{if (k>maxn) maxn=k;  if (x>1&&a[x-1][y]-a[x][y]==o) dfs(x-1,y,k+1,o);if (x<n&&a[x+1][y]-a[x][y]==o) dfs(x+1,y,k+1,o);if (y>1&&a[x][y-1]-a[x][y]==o) dfs(x,y-1,k+1,o);if (y<m&&a[x][y+1]-a[x][y]==o) dfs(x,y+1,k+1,o);  return;
} 
int main()
{n=read();m=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)a[i][j]=read();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)  {//确认方向，求出差值if (i>1&&a[i-1][j]>a[i][j]) dfs(i-1,j,2,a[i-1][j]-a[i][j]); if (i<n&&a[i+1][j]>a[i][j]) dfs(i+1,j,2,a[i+1][j]-a[i][j]);if (j>1&&a[i][j-1]>a[i][j]) dfs(i,j-1,2,a[i][j-1]-a[i][j]);if (j<m&&a[i][j+1]>a[i][j]) dfs(i,j+1,2,a[i][j+1]-a[i][j]);}if (maxn==0) maxn=1; printf("%d",maxn); return 0;
}