`
leili
  • 浏览: 179434 次
社区版块
存档分类
最新评论

HDU 1175

阅读更多

题目: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;}


分享到:
评论

相关推荐

    HDU-GO-crx插件

    语言:中文 (简体) 身在杭电必用的Chrome插件! HDU-GO是一款适用于杭州电子科技大学选课系统的Chrome拓展程序,具有自动抢课、自动学评教、自动计算学分功能。

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    算法-连连看(HDU-1175)(包含源程序).rar

    本压缩包中的资源——"算法-连连看(HDU-1175)(包含源程序).pdf"很可能提供了一个关于如何用编程语言实现连连看算法的详细讲解,包括源代码示例。 连连看算法的实现主要分为以下几个步骤: 1. **游戏初始化**:...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    HDU图论题目分类

    * 题目1175:连连看,涉及到图的最短路径算法。 * 题目1180:诡异的楼梯,涉及到图的单源最短路径概念。 7. 图的最小生成树:图的最小生成树算法、图的 Kruskal 算法等。 * 题目1195:Open the Lock,涉及到图的...

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

Global site tag (gtag.js) - Google Analytics