`

HDU 1728 逃离迷宫 .

 
阅读更多

逃离迷宫

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3619    Accepted Submission(s): 860

Problem Description
  给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?
 


 

Input
  第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,
  第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对应行。
 


 

Output
  每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。
 


 

Sample Input
2 5 5 ...** *.**. ..... ..... *.... 1 1 1 1 3 5 5 ...** *.**. ..... ..... *.... 2 1 1 1 3
 


 

Sample Output
no yes
 

一个杯具。超低B错误!!!!!!!好彩提前出现!!!!!大家一定要记住啊!{=___=}

尼条题,首先就念到就系BFS,标记方向,比较弯数剪枝,考虑卖Start==End,100 100 测试数据都无错。

但系就一直死错!!!!!!!

跟住我就捻系唔系算法错误呢?跟住又捻左一个方法,就系一开始就走同一方向走到底。测试结果全对!!!!!!!!但系又系一直死错!!!!!点解!!!!!天啊~~~!!!!!!!

我蛋裂拉!!!!!!!!!!!

跟住我死命睇………………都系无错………………无错!!!!!!!!!!!

再跟住我绝望………………

我好颓废甘将几个数据合埋几个一起测试(我自己整d测试数据通常系t=1)

第一次:

2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3

5 7
..*...*
.*....*
..*...*
..**..*
.......
3 1 1 3 2

答案:

no

yes

无错……………………

第二次:

2
5 7
..*...*
.*....*
..*...*
..**..*
.......
3 1 1 3 2

5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3

答案:

yes

no

!!!!!!!错左!!!!!点解!!!!跟住单独测试:

1

5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3

答案:

yes

!!!!!!!!!!!哦!!!!!!!!我知啦!!!!!!!扑街!!!!!!!!!!

son of the bitch!!!!!!!!!!!!!!!!fuck you ass hole!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

!!!!!!!!!!!!!!!!!!!!!ばがやる!!!!!!

我终于知道我错左咩拉{=______=}凸,其实就系队列ge定义位置问题………………

一开始我系定义全局变量,如果答案系no,第一个样例ge数据会全部出列,但系!!!如果第一个样例系yes!!!就会中途return!!!!队列里面中有剩余ge元素!!!就会影响下一个样例

跟住改左再上交…………………………AC,死……………………扑……………………街

 

HDU 1728 31ms 364K 1384B C++ 10SGetETernal{(。)(。)}!

 

#include<queue>
#include<iostream>
using namespace std;

struct node { int x,y,dx,dy; } in,temp;

char map[102][102];
int turn[102][102];
int move[4][2]={0,1,1,0,0,-1,-1,0};
int i,j,m,n,k,sx,sy,ex,ey,x,y,T_turn;
bool flag;

//queue<node>q;         //就系呢个杯具WA n次

bool BFS()
{
    queue<node> q;       //改左就AC
    in.x=sx-1; in.y=sy-1; in.dx=-2; in.dy=-2; 
    turn[in.x][in.x]=-1;      //因为系一直走到底,所以出列后就一定转弯。
    q.push(in);
    while (!q.empty())
    {
        in=q.front();
        q.pop();
        T_turn=turn[in.x][in.y]+1;
  if (turn[in.x][in.y]>k) return 0;
        for (i=0;i<4;i++)
        {
            x=in.x+move[i][0]; y=in.y+move[i][1];
            while (x>-1 && y>-1 && x<m && y<n && map[x][y]=='.')
            {
                if (turn[x][y]==-1){                                //-1姐系未访问过ge点
                    if (x==ex-1 && y==ey-1 && T_turn<=k) return 1;   //呢个都系帮凶。
                    temp.x=x; temp.y=y; turn[x][y]=T_turn;   //改变turn[x][y]值同标记有同样效果,防止同一点多次入列。
                    q.push(temp);
                }
                x+=move[i][0]; y+=move[i][1];
            }
        }
    }
    return 0;
}

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&m,&n);
        for (i=0;i<m;i++) scanf("%s",map[i]);
        for (i=0;i<m;i++)
            for (j=0;j<n;j++)
                turn[i][j]=-1;             //初始化turn数组-1为未访问
        scanf("%d%d%d%d%d",&k,&sy,&sx,&ey,&ex);
  if (sx==ex && sy==ey) puts("yes");  //考虑起点等于终点
        else puts(BFS()?"yes":"no");
    }
    return 0;
}

 

 

AC之后我就捻我先前果个算法系唔系都系呢个错呢?………………实践中………………

分享到:
评论

相关推荐

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    大学期间操作系统实验-HDU操作系统实验.zip

    HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-HDU操作系统实验.zip大学期间操作系统实验-...

    hangdianACM.rar_hangdiana_hdu acm_www.hangdianacm_杭电

    这个压缩文件包含的是作者个人提交并解决的ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)题目,这些题目来源于HDU的在线编程平台。 【描述】"杭电的一些acm题目,都是我自己一个一...

    HDU-ACM课件.rar

    HDU-ACM课件.rar 是一个专门为编程竞赛爱好者准备的资源包,主要涵盖了ACM(国际大学生程序设计竞赛)中常见的算法知识。这个压缩包包含了一系列与算法相关的主题,旨在帮助初学者理解和掌握基础及进阶算法。下面将...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU-ACM_java.rar_hdu

    【标题】"HDU-ACM_java.rar" 是一个针对杭州电子科技大学(HDU)ACM竞赛的资源压缩包,其中包含的是使用Java语言编写的算法解决方案。这个压缩包主要面向那些参与或准备参与ACM国际大学生程序设计竞赛(ICPC)的参赛...

    HDU-GO v19.1225.2.zip

    【HDU-GO v19.1225.2.zip】是一个针对杭州电子科技大学(HDU)选课系统的浏览器插件,版本号为v19.1225.2。这个插件的主要功能是优化和提升学生在进行网络选课时的体验,它可能包含了增强界面、自动化操作、数据解析...

    算法-数塔(HDU-2084).rar

    标题中的“算法-数塔(HDU-2084)”是指一个编程竞赛题目,源自杭州电子科技大学(HDU)的在线编程平台。在这个问题中,参赛者被要求解决一个名为“数塔”的算法挑战。数塔问题通常涉及到递归、深度优先搜索(DFS)...

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

    【压缩包子文件的文件名称列表】只有一个文件名 "hdu",这可能是一个目录或者压缩包内其他文件的父目录,也可能是因为压缩包内的其他文件没有列出。 综合以上信息,我们可以推测这个压缩文件包含的 "HDU 1089.cpp" ...

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    HDU-1535-.zip_多源点

    标题中的"HDU-1535-.zip_多源点"表明这是一个关于解决 ACM (国际大学生程序设计竞赛)问题的程序代码包,问题编号为 HDU 1535,且该问题涉及到多源点的最短路径计算。描述中提到的"求多源点到单终点的最短路(反向...

Global site tag (gtag.js) - Google Analytics