【题解】CF374C Inna and Dima

题面传送门

解决思路

本题是找最长路的图上问题，所以先考虑如何建图。

首先把每一个字母转化为数字，然后对于每一个点枚举四个方向，如果有下一个字母，就向那个点建一条边，可以用 \(vector\) 存图比较方便。用数字标号，只需要判断 \(t_{x2,y2}=(t_{x1,y1}+1)\mod 4\) 是否成立即可，但直接用字母判断也是比较方便的。

然后考虑 \(\text{dfs}\) 搜索可以走的最长路。有以下几个注意点：

开始搜索的点一定是 D。
已经更新过答案的点就不用搜了，直接 \(\text{return}\)，也算一个剪枝过程。
可以选无数个点的情况就是出现环了。所以需要 \(vis\) 数组标记本次搜索经过的点，如果走到已经走过的点，直接输出 Poor Inna! 结束程序。同时回溯时记得要把 \(vis\) 清空。
搜索时答案记录为走过的点数比较方便。因为从 D 开始，所以记 \(ans=\max\{dis_{i,j}\}\)。最后若 \(ans<4\) 即输出 Poor Dima!，否则 \(ans \div 4\) 就是 DIMA 的数量。

这样就可以愉快地通过本题了。

AC Code

#include<bits/stdc++.h>

using namespace std;

int n,m,t[1005][1005],dis[1005][1005],ans;

bool vis[1005][1005];

char c;

int X[4]={0,0,1,-1},Y[4]={1,-1,0,0};

struct node{

	int x,y;

};

vector<node> a[1005][1005];

void read(){

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>c;

			if(c=='D') t[i][j]=0;

			if(c=='I') t[i][j]=1;

			if(c=='M') t[i][j]=2;

			if(c=='A') t[i][j]=3;

		}

	}

}

bool cango(int x1,int y1,int x2,int y2){   //能不能走

	if(t[x2][y2]==(t[x1][y1]+1)%4) return 1;

	return 0;

}

void build(){   //建图部分

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			for(int z=0;z<4;z++){

				int xx=i+X[z],yy=j+Y[z];

				if(xx>n||xx<1||yy>m||yy<1) continue;

				if(cango(i,j,xx,yy)) a[i][j].push_back({xx,yy});

			}

		}

	}

}

void dfs(int sx,int sy){    //dfs

	if(dis[sx][sy]) return;

    vis[sx][sy]=1;

    dis[sx][sy]=1;

    for(int i=0;i<a[sx][sy].size();i++){

        int jx=a[sx][sy][i].x,jy=a[sx][sy][i].y;

        if(vis[jx][jy]){    //出现环

			printf("Poor Inna!");

			exit(0);

		}

        dfs(jx,jy);

        dis[sx][sy]=max(dis[sx][sy],dis[jx][jy]+1);

        ans=max(ans,dis[sx][sy]);

    }

    vis[sx][sy]=0;  //vis清零

}

int main(){

	scanf("%d%d",&n,&m);

	read();

	build();

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++) if(!t[i][j]) dfs(i,j); //对每一个D搜索

	}

	if(ans<4) printf("Poor Dima!");

	else printf("%d",ans/4);

	return 0;

}

巴特西

【题解】CF374C Inna and Dima

题面传送门

解决思路

AC Code

最新文章

热门文章