加载中…POJ PKU 2157 广搜
(2011-07-10 16:49:34)
标签：
pojpku2157广搜it |
分类： 搜索 |
题目描述：
一个迷宫中，最多可能有5种门，每种门还有自己对应的钥匙，问能不能到达终点。
解题报告：
只用写一个bfs
如果这次bfs能到终点，直接输出yes
否则，如果这次bfs能拿到钥匙或者开门（使地图有所改变），这继续bfs
再否则（bfs什么成果也没有），直接输出no
代码如下：
memset(vst, 0, sizeof(vst));
int
head = 0, tail = 0;
vst[pos[0]][pos[1]] = 1;
que[tail][0] = pos[0]; que[tail++][1] =
pos[1];
int
flag = 0;
while(head < tail)
{
for(int i = 0; i
< 4; i++)
{
int tmpa = que[head][0] + move[i][0];
int tmpb = que[head][1] + move[i][1];
char x = jeo[tmpa][tmpb];
if (tmpa >= 0
&& tmpa < m
&& tmpb >= 0
&& tmpb < n
&&
!vst[tmpa][tmpb] && x != 'X')
{
if (x ==
'G') return 1;
else if (x
== '.' || x >= 'a'
&& x <= 'e' ||
(x >= 'A'
&& x <= 'E'
&& nowkey[x - 'A'] == key[x -
'A']))
{
if (x >= 'a'
&& x <= 'e')
nowkey[x - 'a']++;
if (x != '.') flag = 2;
vst[tmpa][tmpb] = true;
jeo[tmpa][tmpb] = '.';
que[tail][0] = tmpa;
que[tail++][1] = tmpb;
}
}
}
head++;
}
return
flag;
while(scanf("%d%d", &m,
&n) && (m ||
n))
{
memset(key, 0,
sizeof(key));
memset(nowkey, 0,
sizeof(nowkey));
for(int i = 0; i
< m; i++)
{
scanf("%s", jeo[i]);
for(int j = 0; j < n; j++)
{
if
(jeo[i][j] == 'S')
pos[0] = i, pos[1] = j,
jeo[i][j] = '.';
if
(jeo[i][j] >= 'a' &&
jeo[i][j] <= 'e')
key[jeo[i][j] - 'a']++;
}
}
while(true)
{
int tmp = bfs();
if (tmp == 0)
{
printf("NO\n");
break;
}
if (tmp == 1)
{
printf("YES\n");
break;
}
}
}
return
0;
一个迷宫中，最多可能有5种门，每种门还有自己对应的钥匙，问能不能到达终点。
解题报告：
只用写一个bfs
如果这次bfs能到终点，直接输出yes
否则，如果这次bfs能拿到钥匙或者开门（使地图有所改变），这继续bfs
再否则（bfs什么成果也没有），直接输出no
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m, n, key[5], nowkey[5], pos[2], que[20 * 20][2];
char jeo[20][20], vst[20][20];
int move[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
//返回1， 到达，返回2，表示有进展（开门或者拿钥匙)
int bfs()
{
}
int main()
{
}
喜欢
0
赠金笔