关于P1605的BFS做法
legends·never·die
2018-07-05 07:21:33
虽然迷宫这道题放在dfs的试练场里,但是bfs显然也是可以写出来的。现在大家看一下代码
```cpp
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,k,x,y,a,b,ans;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
bool vis[6][6];
struct oo{
int x,y,used[6][6];
};
oo sa;
void bfs()
{
queue<oo> q; //定义结构体后,可以直接使用结构体名定义变量或者队列。
sa.x = x;
sa.y = y; //横纵坐标替换,这样写起来方便。
sa.used[x][y] = 1;//标记走过的路径
q.push(sa);
while(!q.empty())
{
oo now = q.front(); //一起拿出来
q.pop();
for(int i = 0;i < 4; i++)
{
int sx = now.x + dx[i];
int sy = now.y + dy[i];
if( now.used[sx][sy]
|| vis[sx][sy]
|| sx == 0 || sy == 0
|| sx > n || sy > m)
continue; //如果这里走过,或者这里是障碍,或者这里是墙壁,那么这里就不能走。
if(sx == a && sy == b)
{
ans++; 如果这里是终点,那么结果数量加一
continue;
}
sa.x = sx;
sa.y = sy;
memcpy(sa.used,now.used,sizeof(now.used));
sa.used[sx][sy] = 1; //这里的操作都是为了标记路径
q.push(sa);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d%d%d",&x,&y,&a,&b); //虽然这里可以合并成一个句子,但是由于我是从python转过来的,建议大家以后写代码都设置一个界限,代码不宜太长
for(int i = 1,aa,bb;i <= k; i++) //大家注意一下,我现在是直接把变量定义在循环里面。
{
scanf("%d%d",&aa,&bb); //现在我们不能走障碍了。
vis[aa][bb] = 1;
}
bfs();
printf("%d",ans);
return 0;
}
```
输入输出为什么不用标准输入输出流而用格式化输入输出,嗯~..因为这样比较快吧,不这样写可能会T掉,不过大家可以试一试
现在这个题就解出来了,本人是第一次写题解,如果有什么地方没有解释清楚可以再问我,多提意见,接下来将会改进的更好