C - Digital Path 計蒜客 - 42397

題意：

題意就是給出一個n ? m的數字矩陣每個矩陣元素之間只能上下左右走，而且下一個位置必須比當前位置的數字大1，入口和出口必須數邊緣元素，求可以有多少條路徑。

題解：

第一反應dfs，dfs+記憶化搜索+剪枝
vis[x][y]=1表示這個點能作為dfs的起點

代碼:

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=1e6+9; int vis[2000][2000]; int n,m; int a[2000][2000]; int dp[2000][2000]; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; int sum=0; bool f=0; inline int dfs(int x,int y,int tot) {if(dp[x][y])return dp[x][y];dp[x][y]=0;ll ans=0;int pp=0;for(int i=0;i<4;i++){int newx=x+dx[i];int newy=y+dy[i];if(newx>n||newx<1||newy>m||newy<1)continue;if(a[newx][newy]==a[x][y]+1){pp=1;ans=ans+dfs(newx,newy,tot+1);ans=ans%mod;} }if(tot>=4&&pp==0)//如果長度大于4且已走到頭 {return 1; }dp[x][y]+=ans;return dp[x][y]%mod; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<4;k++){int newx=i+dx[k];int newy=j+dy[k];if(newx>n||newx<1||newy>m||newy<1)continue;if(a[newx][newy]==a[i][j]-1){vis[i][j]=1;}}}}ll ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(vis[i][j]==0){dp[i][j]=dfs(i,j,1);ans=ans+dp[i][j];ans=ans%mod;}}}cout<<ans%mod; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的C - Digital Path 计蒜客 - 42397 05-29的全部內容，希望文章能夠幫你解決所遇到的問題。

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