题目:http://acm.hdu.edu.cn/showproblem.php?pid=1175
简单DFS....直接计算能到当前这个点的最小转折次数就可以了、
下面是AC代码:
#include<iostream>#include<queue>using namespace std;int map[1010][1010];int cnt_map[1010][1010];int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};int s_x,s_y;int e_x,e_y;int flag,n,m;struct node{ int cnt; int x,y; int pre_dir;}s_pos;bool cheak(int x,int y){ if(x>=1&&x<=n&&y>=1&&y<=m&&(map[x][y]==0||x==e_x&&y==e_y)) return true; return false;}void dfs(int x,int y,int cnt,int pre_dir){ if(flag||cnt>3) return ; if(x==e_x&&y==e_y){ flag=1; return ; } for(int i=0;i<4;i++){ int n_x,n_y; n_x=x+dir[i][0]; n_y=y+dir[i][1]; if(cheak(n_x,n_y)&&cnt+1<=cnt_map[n_x][n_y]){ if(pre_dir==i&&cnt<=3&&cnt<cnt_map[n_x][n_y]) { cnt_map[n_x][n_y]=cnt; dfs(n_x,n_y,cnt,pre_dir); } if((pre_dir!=i||pre_dir==-1)&&cnt<=3) { cnt_map[n_x][n_y]=cnt+1; dfs(n_x,n_y,cnt+1,i); } } }}int main(){ int i,j,q; while(cin>>n>>m,n+m){ for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&map[i][j]); scanf("%d",&q); while(q--){ // memset(visited,0,sizeof(visited)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) cnt_map[i][j]=100000; scanf("%d%d%d%d",&s_x,&s_y,&e_x,&e_y); // cout<<cnt_map[1][1]<<endl; if(map[s_x][s_y]!=map[e_x][e_y]||map[s_x][s_y]==0||map[e_x][e_y]==0){ puts("NO"); } else{ flag=0; // visited[s_x][s_y]=1; dfs(s_x,s_y,0,-1); if(flag) puts("YES"); else puts("NO"); } } } return 0;}
分享到:
相关推荐
语言:中文 (简体) 身在杭电必用的Chrome插件! HDU-GO是一款适用于杭州电子科技大学选课系统的Chrome拓展程序,具有自动抢课、自动学评教、自动计算学分功能。
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
本压缩包中的资源——"算法-连连看(HDU-1175)(包含源程序).pdf"很可能提供了一个关于如何用编程语言实现连连看算法的详细讲解,包括源代码示例。 连连看算法的实现主要分为以下几个步骤: 1. **游戏初始化**:...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
hdu2101AC代码
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
* 题目1175:连连看,涉及到图的最短路径算法。 * 题目1180:诡异的楼梯,涉及到图的单源最短路径概念。 7. 图的最小生成树:图的最小生成树算法、图的 Kruskal 算法等。 * 题目1195:Open the Lock,涉及到图的...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...