Digital Path(2019南京C题)

链接:https://nanti.jisuanke.com/t/42397
题意:求图中所要求的线段的数量
题解:dfs+dp,第一次知道dp还能这样玩.....
对于每一位置先判断是否为起点,如果上下左右进入数量为1即为起点
下来因为要求要长度最少为4,所以开三维dp数组进行计数
表示对于第i行第j列的位置,以此为终点的长度为k的情况有多少个
下来就是对于起点进行广搜,对于可以到达的每个点都进行dp数组更新,如果到那个位置他的入度变为0,加入数组,因为如果入度不为0直接加入会有后效性,影响结果

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10,p=1e9+7;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int n,m,g[N][N],in[N][N],out[N][N],dp[N][N][5],res;
void top_sort(){
    queue<pair<int,int> > q;
    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    if(!in[i][j]){
        q.push({i,j});    dp[i][j][1]=1;
    }
    while(q.size()){
        int ux=q.front().first,uy=q.front().second; q.pop();
        for(int i=0;i<4;i++){
            int tx=ux+dx[i],ty=uy+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&g[tx][ty]==g[ux][uy]+1){
                dp[tx][ty][2]=(dp[tx][ty][2]+dp[ux][uy][1])%p;
                dp[tx][ty][3]=(dp[tx][ty][3]+dp[ux][uy][2])%p;
                dp[tx][ty][4]=(dp[tx][ty][4]+dp[ux][uy][3]+dp[ux][uy][4])%p;
                if(--in[tx][ty]==0)    q.push({tx,ty});
            }
        }
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    scanf("%lld",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++){
                int tx=i+dx[k],ty=j+dy[k];
                if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
                    if(g[tx][ty]==g[i][j]+1)    out[i][j]++;
                    if(g[tx][ty]==g[i][j]-1)    in[i][j]++;
                }
            }
    top_sort();
    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    if(!out[i][j]){
        res=(res+dp[i][j][4])%p;
    }
    cout<<res<<endl;
    return 0;
}