首页 > 代码库 > EOJ 3260 袋鼠妈妈找孩子

EOJ 3260 袋鼠妈妈找孩子

暴力搜索。

主要目的就是找到任意一条路径,使得路径长度大于等于$k+1$,写个爆搜发现很快能出解。判断某点是否可走,需要看四周有没有已经走过的点的$dis$比这个点的$dis$小$2$或者$2$以上。

#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;int dis[10][10];int dir[4][2]={	{1,0},	{-1,0},	{0,1},	{0,-1}};int n,m,sx,sy,k,suc;bool ok(int x,int y){	if(x>=1&&x<=n&&y>=1&&y<=m) return 1;	return 0;}bool check(int x,int y){	for(int i=0;i<4;i++)	{		int tx = x + dir[i][0];		int ty = y + dir[i][1];		if(ok(tx,ty)==0) continue;		if(dis[tx][ty] == 0) continue;		if(dis[x][y] - dis[tx][ty]>1) return 0;	}	return 1;}void dfs(int x,int y,int dep){	//printf("%d %d %d\n",x,y,dep);	if(check(x,y)==0) return ;	if(x==sx&&y==sy)	{		if(dep-1<k) return ;		suc=1; return ;	}	for(int i=0;i<4;i++)	{		int tx = x + dir[i][0];		int ty = y + dir[i][1];		if(ok(tx,ty)==0) continue;		if(dis[tx][ty]) continue;		dis[tx][ty] = dep + 1;		dfs(tx,ty,dep+1); if(suc) return ;		dis[tx][ty] = 0;	}}int main(){	scanf("%d%d",&n,&m);	scanf("%d%d%d",&sx,&sy,&k);	dis[1][1] = 1;	dfs(1,1,1);	for(int i=1;i<=n;i++)	{		for(int j=1;j<=m;j++)		{			if(dis[i][j]) printf(".");			else printf("*");		}		printf("\n");	}	return 0;}

EOJ 3260 袋鼠妈妈找孩子