hdu 1254(搜索问题)
最编程
2024-03-27 13:48:16
...
推箱子
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7062 Accepted Submission(s): 2009
Problem Description
推
箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工
只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
Input
输
入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2&
lt;=M,N<=7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代
表箱子要被推去的位置,4代表搬运工的起始位置.
Output
对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1.
Sample Input
1
5 5
0 3 0 0 0
1 0 1 4 0
0 0 1 0 0
1 0 2 0 0
0 0 0 0 0
Sample Output
4
Author
好多坑的一道题。。。很好的一道题。。。参考了别人的代码。。真的做不出来。。。每次结点存个新的图。。get。。。做了才知道。。。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <queue> #include <algorithm> using namespace std; int n,m; int graph[8][8]; bool flag[8][8][4]; bool vis[8][8]; int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}}; struct Node { int x,y; int step; int g[10][10]; }s,person,t; bool check(int x,int y) { if(x<0||x>=n||y<0||y>=m) return false; return true; } bool bfs2(Node s,Node target){ person = s; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(person.g[i][j]==4){ person.x = i; person.y = j; person.step = 0; } } } queue<Node>q; memset(vis,false,sizeof(vis)); q.push(person); vis[person.x][person.y] = true; while(!q.empty()){ Node now = q.front(); q.pop(); if(now.x==target.x&&now.y==target.y){ return true; } Node next; for(int i=0;i<4;i++){ next.step = now.step+1; next.x = now.x +dir[i][0]; next.y = now.y + dir[i][1]; if(!check(next.x,next.y)||s.g[next.x][next.y]==2||vis[next.x][next.y]||s.g[next.x][next.y]==1) continue; vis[next.x][next.y] = true; q.push(next); } } return false; } int bfs(){ memset(flag,false,sizeof(flag)); queue <Node> q; q.push(s); while(!q.empty()){ Node now = q.front(); q.pop(); if(now.x==t.x&&now.y==t.y) return now.step; Node next,target; for(int i=0;i<4;i++){ next = now; next.x = now.x+dir[i][0]; next.y = now.y+dir[i][1]; next.step = now.step+1; if(!check(next.x,next.y)||flag[next.x][next.y][i]||next.g[next.x][next.y]==1) continue; ///该方向已经走过了 ///人的目标点(人以此点为目标点将箱子从now推向next) target.x = now.x - dir[i][0]; target.y = now.y - dir[i][1]; if(!check(target.x,target.y)) continue; if(bfs2(next,target)){ swap(next.g[now.x][now.y],next.g[next.x][next.y]); swap(next.g[target.x][target.y],next.g[person.x][person.y]); flag[next.x][next.y][i] = true; q.push(next); } } } return -1; } int main() { int tcase; scanf("%d",&tcase); while(tcase--) { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) for(int j=0; j<m; j++){ scanf("%d",&s.g[i][j]); if(s.g[i][j]==2){ s.x = i; s.y = j; s.step = 0; } if(s.g[i][j]==3){ t.x = i; t.y = j; } } int res = bfs(); printf("%d\n",res); } }
推荐阅读
-
HDOJ 水问题集 7:背诵搜索
-
[HDU 1427] 速度计算 24 点(DFS 暴力搜索)
-
我今天遇到了一个小问题(在网上搜索了一下才明白)
-
基于 SA 模拟退火算法的多车辆 TSP 问题 Matlab 仿真,实现多车辆单独搜索最优路径
-
iCloud 切换区域,中国区保留 appStore(更新)--自 2018 年 2 月 28 日起,中国区 iCloud 由云上贵州管理 苹果公司发布的公告 https://support.apple.com/zh-cn/HT208352 关键词 关键部分 受影响的 iCloud 账户:国家或地区设置为 "中国 "的 Apple ID。 iCloud 包含的服务照片、邮件、通讯录、日历、提醒事项、备忘、书签、钱包、钥匙串、云备份、云驱动器、应用程序数据 新条款和条件: 同意仅出于本协议允许的目的并在中国法律允许的范围内使用服务。 云桂洲在提供服务时应使用合理的技能并尽职尽责,但在适用法律允许的最大范围内,我们不保证或担保您通过本服务存储或访问的任何内容不会意外损坏、崩溃、丢失或根据本协议的条款被删除,如果发生此类损坏、崩溃、丢失或删除,我们不承担任何责任。您应自行负责维护您的信息和数据的适当备份。 Apple 和云上贵州有权访问您存储在服务中的所有数据,包括有权根据适用法律相互之间共享、交换和披露所有用户数据(包括内容)。 本协议的解释、效力和履行应适用*法律。对于因本协议引起的或与本协议有关的任何争议,云桂洲和您同意提交中国国际经济贸易仲裁委员会(CIETAC)根据提交仲裁时有效的法律在北京进行具有约束力的仲裁。 由云桂洲管理,用户选择: 停用; ID 到地区; 受 iCloud(由云桂洲运营)条款和条件约束 首先,我想说说我对数据安全的看法。 当我在朋友圈发布通知时,有些朋友回复说国外的操作并没有多安全,或者国外的安全只是相对于国外而言的等等。首先,我非常感谢这些朋友,这让我反思什么是数据安全。以下观点均属个人观点: 国外的月亮一定比国内圆? 这是一个根深蒂固的问题,只要有人说国外的东西比国内好,就会有人嘲笑崇洋媚外。我觉得我们在某些方面应该向国外学习,比如搜索引擎和版权问题。打开百度搜索 "数据安全",第一行肯定是广告。打开谷歌搜索 "数据安全",第一条就是 "数据安全_百度百科" .....各种版权问题大家都明白,支持正版,但不仅客户一心想找免费破解,就连作者也往往没有保护自己劳动成果或产品的想法。但从另一个层面来说,国内的发展和安全,甩国外几条街。没有说哪里好,哪里不好,辩证地去学习更好。 国外也有别有用心的数据泄露,谈何安全? 从加密解密的角度看,自古以来就没有绝对安全的加密,只有相对安全的做法。苹果的棱镜门、微软的 cpu 漏洞,各种参差不齐的被破解案例 ....是的,这的确是一个很好的论据,但凡事都不能只看一面,当年苹果面对FBI破解手机的要求,几经论证,苹果还是拒绝破解。这点拿到国内,只要上面的文件传达下去,还有企业敢说不吗?还敢说不吗? 关于这次iCloud数据迁移个人看法? 把数据迁移到贵州的云端,相当于把手机的所有数据都存储在贵州的云端服务器上。也许访问数据的速度会快很多,但我会把我的iCloud区放到美国,因为我不想数据存在云上贵州后经常接到莫名其妙的电话或短信,更不想因为乱用国外服务器而被请去喝茶。iCloud一个ID,即从中国账号转到美国区,主要用于数据存在美国服务器上。appStore一个ID,除了注册一个中国ID外,专门用来下载应用用,因为国外ID不支持酷狗和网易云等应用。麻烦的是,用了新的 appStore ID 后,当前的应用还得重新下载安装,因为旧的应用 ID 与新的应用 ID 不兼容,安装不了。最后,iCloud迁移后,国内用户使用美国服务器,估计要 "扶墙 "了。 专业步骤: 首先,进行appleID设置,这是前提条件,否则无法选择转移区域! 取消 appleID 的双重认证 取消家庭共享选项 二、窗口下载并安装 icloud 3.0 版
-
Ask Cucumber 在安装 "与编辑器兼容的搜索市场(*.feature)"时遇到问题。EN
-
经典算法 ----- 农民过河问题(深度优先搜索)
-
InfoQ,谈谈百度开源高性能搜索引擎 Puck-Ben:Puck是团队长期研究和努力的成果,作为Puck的负责人,我对这个项目有着深深的热爱和执着,对我个人而言,它不仅仅是一个搜索引擎,而是代表着团队心血和智慧的结晶,它是我们对技术的追求,对创新的执着,也是我们对未来的期望和愿景,Puck的每一次升级和优化都记录着我们的成长和进步。这是我们对技术的追求,对创新的执着,也是我们对未来的期望和憧憬,帕克的每一次升级和优化都记录着我们的成长和进步。 我对帕克的未来充满期待。首先,我希望 Puck 能够在开发者社区得到广泛应用,同时得到社区的反馈,不断优化和改进。我期待看到更多的人参与到Puck的开发和使用中来,通过大家的共同努力,让Puck成为人工智能领域有影响力的工具。其次,我希望Puck能够不断创新和优化,保持技术领先地位,不仅要适应当前的技术需求,更要预测和引领未来的技术趋势。最后,我希望Puck能在更多的实际应用中实现自身价值,为人工智能在各行各业的应用提供有力支撑,推动科技发展。 访谈嘉宾简介: Ben,百度搜索内容技术部主任架构师,负责多模态内容理解、超大规模内容关系计算、内容处理与生成、模型优化等方向。 欢迎加入朋克技术交流群:913964818 本部门招聘ANN搜索工程师、模型优化工程师、分布式计算研发工程师等多个职位。欢迎勇于接受挑战、具有优秀分析和解决问题能力的人才加入我们。 招聘邮箱:tianyakun@baidu.com --END-- 推荐阅读
-
HDU2952 (深度搜索)
-
hdu 3307(欧拉函数 + 好问题)