杭电OJ1010不能用BFS么？解决方案
杭电OJ1010不能用BFS么？
新手一枚。刚开始没看清题。直接就BFS了，结果WA了。最后发现看错题了。是正好在T秒的时候到出口。
http://acm.hdu.edu.cn/showproblem.php?pid=1010
这道题不能用BFS么。只能DFS+剪枝？
我的BFS代码：
------解决思路----------------------
不是不能用bfs，用bfs不太好控制。
假设现在有D和G两个点可以进行扩展，选择扩展到A，A然后又扩展到B和C。因为A是由D扩展过来，所以A不能再扩展到D，否则就会进入无限循环。A扩展到B和C后，你的程序中要有标识说明A不能再被扩展，否则不符合题目要求，也会进入死循环。现在问题来了，如果原来从G扩展到A刚好是一个答案，由于现在A被标识为不可再"走“。就造成了你的WA。而使用dfs可以先从D扩展到A，当发现不可行时，在函数回退的同时也可以重新把A标识为可"走"，然后再选择G进行扩展。
新手一枚。刚开始没看清题。直接就BFS了，结果WA了。最后发现看错题了。是正好在T秒的时候到出口。
http://acm.hdu.edu.cn/showproblem.php?pid=1010
这道题不能用BFS么。只能DFS+剪枝？
我的BFS代码：
#include <iostream>
#include <limits.h>
using namespace std;
int Height, Width, T;
enum mark {Black, White, Blue};
//定义迷宫
struct M{
int d;
int color;
}MAZE[8][8];
//定义队列
struct Pos{
int x;
int y;
}QUEUE[36];
int head = 0;
int tail = 0;
void ENQUEUE(struct Pos *, int, int); //入队
struct Pos DEQUEUE(struct Pos *); //出队
//保存起点
struct StartPos{
int x;
int y;
}stPos;
void initializeMaze(int, int); //初始化迷宫
int bfs(const struct StartPos &);
int main()
{
for(int i = 0; i < 8; ++i)
{
for(int j = 0; j < 8; ++j)
{
MAZE[i][j].color = Black;
MAZE[i][j].d = 0;
}
}
while(cin >> Height >> Width >> T)
{
if(0 == Height && 0 == Width && 0 == T)
break;
initializeMaze(Height, Width);
head = 0;
tail = 0;
if(bfs(stPos))
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
void initializeMaze(int Height, int Width)
{
char ch;
for(int i = 1; i <= Height; ++i)
{
for(int j = 1; j <= Width; ++j)
{
cin >> ch;
if('.' == ch)
MAZE[i][j].color = White;
else if('X' == ch)
continue;
else if('S' == ch)
{
stPos.x = i;
stPos.y = j;
}
else
MAZE[i][j].color = Blue;
}
}
}
void ENQUEUE(struct Pos * QUEUE, int x, int y)
{
QUEUE[tail].x = x;
QUEUE[tail].y = y;
tail++;
}
struct Pos DEQUEUE(struct Pos * QUEUE)
{
struct Pos cur;
cur.x = QUEUE[head].x;
cur.y = QUEUE[head].y;
head++;
return cur;
}
int bfs(const struct StartPos & stPos)
{
ENQUEUE(QUEUE, stPos.x, stPos.y);
struct Pos u;
int d;
while(head < tail)
{
u = DEQUEUE(QUEUE);
//判断当前位置上边的点
if(White == MAZE[u.x - 1][u.y].color)
{
MAZE[u.x - 1][u.y].color = Black;
MAZE[u.x - 1][u.y].d = MAZE[u.x][u.y].d + 1;
ENQUEUE(QUEUE, u.x - 1, u.y);
}
else if(Blue == MAZE[u.x - 1][u.y].color)
{
d = MAZE[u.x][u.y].d + 1;
if(d == T)
return 1;
else
return 0;
}
//判断当前位置下边的点
if(White == MAZE[u.x + 1][u.y].color)
{
MAZE[u.x + 1][u.y].color = Black;
MAZE[u.x + 1][u.y].d = MAZE[u.x][u.y].d + 1;
ENQUEUE(QUEUE, u.x + 1, u.y);
}
else if(Blue == MAZE[u.x + 1][u.y].color)
{
d = MAZE[u.x][u.y].d + 1;
if(d == T)
return 1;
else
return 0;
}
//判断当前位置左面的点
if(White == MAZE[u.x][u.y - 1].color)
{
MAZE[u.x][u.y - 1].color = Black;
MAZE[u.x][u.y - 1].d = MAZE[u.x][u.y].d + 1;
ENQUEUE(QUEUE, u.x, u.y - 1);
}
else if(Blue == MAZE[u.x][u.y - 1].color)
{
d = MAZE[u.x][u.y].d + 1;
if(d == T)
return 1;
else
return 0;
}
//判断当前位置右面的点
if(White == MAZE[u.x][u.y + 1].color)
{
MAZE[u.x][u.y + 1].color = Black;
MAZE[u.x][u.y + 1].d = MAZE[u.x][u.y].d + 1;
ENQUEUE(QUEUE, u.x, u.y + 1);
}
else if(Blue == MAZE[u.x][u.y + 1].color)
{
d = MAZE[u.x][u.y].d + 1;
if(d == T)
return 1;
else
return 0;
}
}
return 0;
}
------解决思路----------------------
不是不能用bfs，用bfs不太好控制。
假设现在有D和G两个点可以进行扩展，选择扩展到A，A然后又扩展到B和C。因为A是由D扩展过来，所以A不能再扩展到D，否则就会进入无限循环。A扩展到B和C后，你的程序中要有标识说明A不能再被扩展，否则不符合题目要求，也会进入死循环。现在问题来了，如果原来从G扩展到A刚好是一个答案，由于现在A被标识为不可再"走“。就造成了你的WA。而使用dfs可以先从D扩展到A，当发现不可行时，在函数回退的同时也可以重新把A标识为可"走"，然后再选择G进行扩展。