首页 > 代码库 > ECNU 3260 袋鼠妈妈找孩子(dfs)
ECNU 3260 袋鼠妈妈找孩子(dfs)
链接:http://acm.ecnu.edu.cn/problem/3260/
题意:
给出一个x,y,k。求从左上角到(x,y)最短路径不少于k而且最快到达(x,y)的迷宫。(迷宫有多个 输出其中一个就行)
分析:
因为数据量很少,而且限时很宽,可以考虑dfs。限制是每个要走的格四个方向只能有一个走过的格,其实就是上一个走到这个格子的格,因为如果有多于一个相邻的格子,那么就会从另一个格子走到这格而不是从另一个格子走到上一个格子再走到这格,所以限制条件是成立的。
#include <bits/stdc++.h> using namespace std; int G[10][10]; int n,m,fx,fy,k ,maxx = 9999; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; int ans[10][10]; void dfs(int x,int y,int step) { int cnt = 0,tx, ty; for(int i = 0; i < 4; i++) { tx = x, ty = y; tx += dir[i][0]; ty += dir[i][1]; if(tx < 1 || tx >n || ty<1 || ty > m) continue; if(G[tx][ty]) cnt++; } if(cnt > 1) return; if(x == fx && y == fy && step >= k) { if(step < maxx) { // printf("%d\n", step); maxx = step; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(G[i][j]) ans[i][j] = ‘.‘; else ans[i][j] = ‘*‘; } } } else return; } for(int i = 0; i < 4; i++) { tx = x, ty = y; tx += dir[i][0]; ty += dir[i][1]; if(tx < 1 || tx >n || ty<1 || ty > m || G[tx][ty]) continue; G[tx][ty] = 1; dfs(tx,ty,step+1); G[tx][ty] = 0; } } int main() { memset(G,0,sizeof(G)); scanf("%d %d", &n, &m); scanf("%d %d %d", &fx, &fy, &k); G[1][1] = 1; dfs(1,1,0); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { printf("%c",ans[i][j]); } printf("\n"); } }
ECNU 3260 袋鼠妈妈找孩子(dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。