首页 > 代码库 > 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 袋鼠妈妈找孩子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。