星期日 :
花了一个下午的时间搞 昨天比赛的逃离迷宫问题
虽然做了不少的搜索题,但是这题原来还真不简单
不是一般的搜索方法,不是很适合我做....
17:34分,还没有搞定,希望晚上可以拿下它.
//----------------------------------------
晚22:38分终于干掉了这题,记录一下
花了我10个小时
前后用了N种方法
证明自己还是太菜
其实也是这题很强
小看它了,把它当成一般的搜索
其实有时候搜索很需要变通
还有就是STL的队列虽然好用,但是占MEMERY大
要不是用了STL,也不会在训练的赛的时候MLE浪费了很多时间!
题目:
HDOJ 1728 逃离迷宫 http://acm.hdu.edu.cn/showproblem.php?pid=1728
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
解题过程:
先是用了广度优先搜索的方法,但是当时用了STL的队列,于是MLE了
后来讨论的时候发现可以用记录型深度搜索的方法
但是试过之后,发现一般的记录型深度搜索还是会TLE的
于是再次用广搜,只不过用自己写的队列,还用了二维数组记录
但是考虑了很多问题排了很多BUG之后还是一直WA
主要是广搜对这题并非很好,会有重走或多算的可能.
花了一下午时间不断排除出错可能后未果,绝望了
网上看一下,发现最好对同一方向的一直搜索一下去的方法很好
这样做的最大好处是”最小转弯优先” ,这样可以避免了一般广搜的很大不足
AC CODE:
#include <iostream>
using namespace std;
char g[102][102]; //记录图
int step[102][102]; //记录step
struct Node
{
int x;
int y;
int dir;
int last;
}state[10002];
//g[行][列]
int k,x1,x2,y1,y2;
int dir[][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool bfs();
int n,m;
int main()
{
int i,j,t;
scanf("%d",&t);
while (t--)
{
scanf("%d %d",&m,&n);
//m行,n列
for (i=0;i<m;i++)
{
scanf("%s",g[i]);
}
scanf("%d %d %d %d %d",&k,&y1,&x1,&y2,&x2);
//反置xy, 使 x1，x2对应行，y1, y2对应列。
x1--;y1--;y2--;x2--;
//-----------------------------------------
memset(step,-1,sizeof(step));
// step[x1][y1] = 0;
if (x1 == x2 && x2 == y2)
{
printf("yes/n");
continue;
}
if(bfs())
{
if (step[x2][y2] <= k)
{
printf("yes/n");
}
else
printf("no/n");
}
else
{
printf("no/n");
}
// for (i=0;i<m;i++)
// {
// for (j=0;j<n;j++)
// {
// printf("%d ",step[i][j]);
// }
// printf("/n");
// }
}
return 0;
}
bool bfs()
{
int head = 0;
int tail = 1;
state[head].x = x1;
state[head].y = y1;
int i;
while (head != tail)
{
for (i=0;i<4;i++)
{
int tx = state[head].x + dir[i][0];
int ty = state[head].y + dir[i][1];
while (g[tx][ty] == '.' && tx>=0 && tx<m && ty>=0 && ty<n)
{
if (step[tx][ty] == -1)
{
state[tail].x = tx;
state[tail].y = ty;
tail++;
step[tx][ty] = step[state[head].x][state[head].y] + 1;
if(tx==x2 && ty==y2)
{
return 1;
}
}
tx += dir[i][0];
ty += dir[i][1];
}
}
head++;
}
return 0;
}
参考网页:
http://hi.baidu.com/185015165/blog/item/247a4d135ad8d8856438db7c.html
星期一:
上一题在训练中没有解出来是我的错
而这道题是我在训练赛时又是重大的失误,所以在这里再做一遍
我只知道我只前看过这个题,当时还不会博弈,没有解出来
但是后来会了博弈之后并没有再找出这个题目
题目:
HDOJ 1730 Northcott Game http://acm.hdu.edu.cn/showproblem.php?pid=1730
Problem Description
Tom和Jerry正在玩一种Northcott游戏，可是Tom