`

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之后我就捻我先前果个算法系唔系都系呢个错呢?………………实践中………………

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics