正題

---

題目大意

有n*m的數字矩陣，要求每次只能往相鄰的格子移動并取數，要求取數的順序是一個等差的上升序列。求最多能移動多少步

---

解題思路

過法：

爆搜卡常

做法：

記憶化用f[i][j][k]表示在第i行第j列朝方向k移動需要的長度，然后記憶化。
詳見：
https://blog.csdn.net/xuxiayang/article/details/80374235#代碼記搜

---

代碼（卡常代碼）

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; int a[102][102],n,m,f[102][102][4],maxs,ns; void dfs(int x,int y,int n,int dep,int mov) {if (dep>maxs)maxs=dep;if (x+1<=ns&&a[x+1][y]-a[x][y]==mov)dfs(x+1,y,a[x][y],dep+1,mov);if (x-1>0&&a[x-1][y]-a[x][y]==mov)dfs(x-1,y,a[x][y],dep+1,mov);if (y+1<=m&&a[x][y+1]-a[x][y]==mov)dfs(x,y+1,a[x][y],dep+1,mov);if (y-1>0&&a[x][y-1]-a[x][y]==mov)dfs(x,y-1,a[x][y],dep+1,mov); } int main() {scanf("%d%d",&ns,&m);n=ns;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf("%d",&a[i][j]);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){ if (a[i+1][j]>a[i][j])dfs(i+1,j,a[i][j],1,a[i+1][j]-a[i][j]);if (a[i-1][j]>a[i][j])dfs(i-1,j,a[i][j],1,a[i-1][j]-a[i][j]);if (a[i][j+1]>a[i][j])dfs(i,j+1,a[i][j],1,a[i][j+1]-a[i][j]);if (a[i][j-1]>a[i][j])dfs(i,j-1,a[i][j],1,a[i][j-1]-a[i][j]);if(maxs==n*m) {printf("%d",maxs); return 0;}}printf("%d",maxs+1);return 0; }

總結

以上是生活随笔為你收集整理的【2018.5.19】模拟赛之三-ssl2434 取数【搜索,卡常或记忆化搜索】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。