HDU 1728 逃离迷宫(DFS)
2018-06-17 22:14:20来源:未知 阅读 ()
题目网址:http://acm.hdu.edu.cn/showproblem.php?pid=1728
题目:
逃离迷宫
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27324 Accepted Submission(s): 6684
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数,(x1, y1), (x2, y2)表示两个位置,其中x1,x2对应列,y1, y2对应行。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 using namespace std; 5 struct node{ 6 int x,y; 7 }dir[4]={{0,1},{-1,0},{1,0},{0,-1}}; 8 9 char maze[105][105]; 10 int n,m,k; 11 int xb,yb,xe,ye; 12 int visited[105][105]; 13 int flag; 14 bool check(int x,int y,int g){//判断该点是否能走 15 if(x<0 || x>=n) return false; 16 if(y<0 || y>=m) return false; 17 if(maze[x][y]!='.') return false; 18 if(g>visited[x][y]) return false; 19 return true; 20 } 21 void dfs(int x,int y,int g,int di){ 22 if(g>k || flag) return ;//根据拐弯数进行剪枝 23 if(x==xe && y==ye){ 24 printf("yes\n"); 25 flag=1; 26 return ; 27 } 28 for (int d=0,xx,yy; d<4; d++) { 29 int tg; 30 xx=x+dir[d].x; 31 yy=y+dir[d].y; 32 tg=g; 33 if(d!=di) tg=g+1;//与前一个点方向不同,拐弯数加一 34 if(check(xx, yy, tg)){ 35 visited[xx][yy]=tg;//及时更新最小拐弯数 36 dfs(xx, yy, tg, d); 37 } 38 } 39 } 40 int main(){ 41 int t; 42 scanf("%d",&t); 43 while (t--) { 44 scanf("%d%d ",&n,&m); 45 for (int i=0; i<n; i++) gets(maze[i]); 46 scanf("%d%d%d%d%d",&k,&yb,&xb,&ye,&xe);//按照平常题目的习惯互换了x,y 47 yb--;xb--;ye--;xe--;//题目给的行列是从1开始,数组从0开始,所以都减一 48 for(int i=0;i<n;i++) 49 for (int j=0; j<m; j++) { 50 visited[i][j]=k+1;//初始化拐弯数为k+1 51 } 52 flag=0; 53 visited[xb][yb]=0;//出发点不需要拐弯 54 dfs(xb,yb,-1,-1); 55 if(!flag) printf("no\n"); 56 } 57 return 0; 58 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash