关于P1605的BFS做法

legends·never·die

2018-07-05 07:21:33

Solution

虽然迷宫这道题放在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掉,不过大家可以试一试 现在这个题就解出来了,本人是第一次写题解,如果有什么地方没有解释清楚可以再问我,多提意见,接下来将会改进的更好