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, x₁, y₁, x₂, y₂ (1 ≤ k ≤ 10, 1 ≤ x₁, x₂ ≤ n, 1 ≤ y₁, y₂ ≤ m),其中k表示gloria最多能转的弯数，(x₁, y₁), (x₂, y₂)表示两个位置，其中x₁，x₂对应列，y₁, y₂对应行。

 

 

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