2019ICPC亚洲区域赛(南京) C-Digital Path 题解

2019ICPC亚洲区域赛(南京) C-Digital Path

题目链接 Digital Path

做这道题的时候Edge浏览器的翻译给我打来了很大的困扰，我再也不用翻译器读题了。（似乎也不太可能）

观察之后的第一想法是BFS，但是再确定BFS的根节点的过程中我发现，这个图看作DAG，入度为０的点就是起点。

然后自然而然地把思路转到了拓扑排序上，在拓扑排序的过程中更新dp数组。

状态转移方程为:

$dp[xx][yy][k]+=dp[x][y][k-1],wherek\le 3$

$dp[xx][yy][4]+=dp[x][y][3]+dp[x][y][4]$

其中$dp[xx][yy][4]$表示以$(xx,yy)$为终点的且长度大于等于4的路径个数。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int MAXN=1e3+5;
struct node{
	int x,y;
	node(int a,int b):  x(a),y(b){}
};
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},n,m,mp[MAXN][MAXN],in[MAXN][MAXN],out[MAXN][MAXN],dp[MAXN][MAXN][5];
queue <node> Q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mp[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<4;k++){
				int newi=i+dx[k],newj=j+dy[k];
				if(newi<1||newi>n||newj<1||newj>m) continue;
				if(mp[i][j]==mp[newi][newj]+1) in[i][j]++;
				if(mp[i][j]==mp[newi][newj]-1) out[i][j]++;
			} 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(in[i][j]==0){
				dp[i][j][1]++;
				Q.push(node(i,j));
			}
	while(!Q.empty()){
		int x=Q.front().x,y=Q.front().y; Q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>n||xx<1||yy>m||yy<1) continue;
			if(mp[xx][yy]!=mp[x][y]+1) continue;
			if(in[xx][yy]!=0){
				dp[xx][yy][1]=0;
				dp[xx][yy][2]=(dp[xx][yy][2]+dp[x][y][1])%MOD;
				dp[xx][yy][3]=(dp[xx][yy][3]+dp[x][y][2])%MOD;
				dp[xx][yy][4]=(dp[xx][yy][4]+dp[x][y][3]+dp[x][y][4])%MOD;
				in[xx][yy]--;
				if(in[xx][yy]==0) Q.push(node(xx,yy));
			}
		}
	}
	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[i][j][4])%MOD;
	cout<<ans;
	return 0;
}

提交了5次才通过,原来是我把1e9+7写成了1e9
队友笑疯了

最后

以上就是懵懂唇膏为你收集整理的2019ICPC亚洲区域赛(南京) C-Digital Path 题解的全部内容，希望文章能够帮你解决2019ICPC亚洲区域赛(南京) C-Digital Path 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。