C.Digital Path

2019 ICPC Nanjing 复现

#include <bits/stdc++.h>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std;
typedef long long ll ;
const int INF = 0x3f3f3f3f , N = 1010 ; void read(int &x)
{
	x = 0 ;
	char c = getchar() ;
	int f = 1 ; while(!isdigit(c)) 
	 {
	 	if(c == '-') f = -1 ;
	 c = getchar() ;
	 } 
	while(isdigit(c)) x = x * 10 + c - 48 , c = getchar() ;
	x *= f ;
}
const int mod = 1e9 + 7 ; struct node
{
	int x , y ; node() {	} 
	node(int xx , int yy) : x(xx) , y(yy) {	} ;
};
int m , n , a[N][N] , dp[5][N][N] , in[N][N] , out[N][N] ; int dir[4][2] = {0 , 1, 0 , -1 , 1 , 0 , -1 , 0} ; bool valid(int x , int y)
{
	if(x < 1 || y < 1 || x > n || y > m) return false ;
	return true ;
} 
void Add(int i , int j , int x , int y)
{
	dp[2][x][y] = (dp[2][x][y] + dp[1][i][j] ) % mod ;
	dp[3][x][y] = (dp[3][x][y] + dp[2][i][j] ) % mod ;
	dp[4][x][y] = (dp[4][x][y] + dp[3][i][j] + dp[4][i][j]) % mod ; 
}
int main()
{

    read(n) , read(m) ;
    for(int i = 1; i <= n ;i ++)
     for(int j = 1; j <= m ;j ++) 
      read(a[i][j]) ;
    queue<node>  q ;
    for(int i = 1; i <= n ;i ++)
     {
     	for(int j = 1; j <= m ;j ++)
     	{
     	 for(int k = 0 ;k < 4; k ++)
     	  {
     	  	int tx = i + dir[k][0] ;
     	  	int ty = j + dir[k][1] ;
     	  	if(!valid(tx , ty)) continue ;
     	  	if(a[tx][ty] == a[i][j] + 1) out[i][j] ++ ;
     	  	if(a[tx][ty] == a[i][j] - 1) in[i][j] ++ ;
		   }
		  if(in[i][j] == 0) 
		   q.push(node(i , j)) , dp[1][i][j] ++ ;	
	    }  
	 }
	 while(q.size())
	 {
	 	node p = q.front() ; q.pop() ;
	 	for(int k = 0 ;k < 4 ;k ++)
	 	 {
	 	 	int tx = p.x + dir[k][0] ;
	 	 	int ty = p.y + dir[k][1] ;
	 	 	if(valid(tx ,ty) == 0) continue ;
	 	 	if(a[tx][ty] != a[p.x][p.y] + 1) continue ;
	 	 	Add(p.x , p.y , tx , ty) ;
	 	 	in[tx][ty] -- ;
			if(in[tx][ty] == 0) q.push(node(tx , ty)) ; 
		 }
	 }
	 int ans = 0 ;
	 for(int i = 1; i <= n ;i ++)
	  for(int j = 1 ; j <= m ;j ++)
	   if(out[i][j] == 0)
	    ans = (ans + dp[4][i][j]) % mod ;
	 printf("%d\n" , ans) ;
	return 0 ;
}