2019ICPC亚洲区域赛(南京) C-Digital Path 题解
发布时间
阅读量：
阅读量
2019ICPC亚洲区域赛(南京) C-Digital Path
题目链接 Digital Path
做这道题的时候Edge浏览器的翻译给我带来了显著的麻烦,我也无需依赖任何翻译工具来解题.(似乎也不太可能)
经过观察后的第一个想法是采用BFS算法；然而，在进一步确定BFS作为根节点的过程中，则发现将其视为一个有向无环图（DAG），其中所有入度为零的顶点即为起始点。
随后自然地转到了拓扑排序的相关讨论，在对拓扑排序进行分析时动态更新dp数组
状态转移方程 为:
dp[xx][yy][k]+=dp[x][y][k-1], \,where\,k≤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
队友笑疯了
全部评论 (0)
还没有任何评论哟~