题目链接

单向bfs就是水题

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = + ;
struct Node
{
int x, y;
};
int g[Max][Max];
int vis[Max][Max];
int n, sx, sy, ex, ey;
int gx[] = {-, -, -, -, , , , };
int gy[] = {-, -, , , , , -, -};
bool in_bound(int x, int y)
{
if (x >= && y >= && x < n && y < n)
return true;
return false;
}
int bfs(int sx, int sy)
{
Node node, temp;
node.x = sx;
node.y = sy;
vis[sx][sy] = ;
queue<Node> q;
q.push(node);
while (!q.empty())
{
node = q.front();
q.pop();
if (node.x == ex && node.y == ey)
return vis[ex][ey];
for (int i = ; i < ; i++)
{
int fx = node.x + gx[i];
int fy = node.y + gy[i];
if (in_bound(fx, fy) && vis[fx][fy] > vis[node.x][node.y] + )
{
temp.x = fx;
temp.y = fy;
vis[fx][fy] = vis[node.x][node.y] + ;
q.push(temp);
}
}
}
return -;
}
int main()
{
int test;
scanf("%d", &test);
while (test--)
{
scanf("%d", &n);
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
memset(vis, INF, sizeof(vis));
printf("%d\n", bfs(sx, sy));
}
return ;
}

单向bfs

做这题主要是学着写双向bfs;

分别从起点和终点开始搜,如果重合即找到

从这个博客学会的

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = + ;
struct Node
{
int x, y;
bool step;
};
// 这个step的意思之前没搞明白,他其实就是指的 在某一步下可以走到点
//开始讲 start.step设为true,因此在只能走一次 8 个点,然后8个点都是第一步走的,然后把最后一个点的step设为true,当你走第二部时候,就是 do { 以这个点扩展 8 步} while ( !current.step) step控制了层数。
int g[Max][Max];
int vis[Max][Max];
int n, sx, sy, ex, ey;
int gx[] = {-, -, -, -, , , , };
int gy[] = {-, -, , , , , -, -};
bool in_bound(int x, int y)
{
if (x >= && y >= && x < n && y < n)
return true;
return false;
}
int bfs()
{
if (sx == ex && sy == ey)
return ;
Node start, finish;
start.x = sx;
start.y = sy;
start.step = true;
finish.x = ex;
finish.y = ey;
finish.step = true;
vis[sx][sy] = ;
vis[ex][ey] = ;
queue<Node> frontSearch;
queue<Node> backSearch;
int fstep = , bstep = ;
frontSearch.push(start);
backSearch.push(finish);
Node current;
while (!frontSearch.empty() || !backSearch.empty())
{
if (!frontSearch.empty())
{
do
{
current = frontSearch.front();
frontSearch.pop();
for (int i = ; i < ; i++)
{
int fx = current.x + gx[i];
int fy = current.y + gy[i];
if (in_bound(fx, fy))
{
if (vis[fx][fy] == )
{
return fstep + bstep + ;
}
if (!vis[fx][fy])
{
vis[fx][fy] = ;
Node temp;
temp.x = fx;
temp.y = fy;
temp.step = false;
frontSearch.push(temp);
}
}
}
}while(current.step == false);
fstep++;
current = frontSearch.front();
frontSearch.pop();
current.step = true; // 为了让最后队列中最后一个数step为true,先将队首拿出来,修改step,然后在入队
frontSearch.push(current);
} if (!backSearch.empty())
{
do
{
current = backSearch.front();
backSearch.pop();
for (int i = ; i < ; i++)
{
int fx = current.x + gx[i];
int fy = current.y + gy[i];
if (in_bound(fx, fy))
{
if (vis[fx][fy] == )
{
return bstep + fstep + ;
}
if (!vis[fx][fy])
{
vis[fx][fy] = ;
Node temp;
temp.x = fx;
temp.y = fy;
temp.step = false;
backSearch.push(temp);
}
}
}
} while(current.step == false);
bstep++;
current = backSearch.front();
backSearch.pop();
current.step = true;
backSearch.push(current);
}
}
return -;
}
int main()
{
int test;
scanf("%d", &test);
while (test--)
{
scanf("%d", &n);
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
memset(vis, , sizeof(vis));
printf("%d\n", bfs());
}
return ;
}

第二种 双向bfs写法:

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int Max = + ;
struct Node
{
int x, y;
bool step;
};
int g[Max][Max];
int fvis[Max][Max], bvis[Max][Max];
int n, sx, sy, ex, ey;
int gx[] = {-, -, -, -, , , , };
int gy[] = {-, -, , , , , -, -};
bool in_bound(int x, int y)
{
if (x >= && y >= && x < n && y < n)
return true;
return false;
}
int bfs()
{
if (sx == ex && sy == ey)
return ;
Node start, finish;
start.x = sx;
start.y = sy;
start.step = true;
finish.x = ex;
finish.y = ey;
finish.step = true;
fvis[sx][sy] = ;
bvis[ex][ey] = ;
queue<Node> frontSearch;
queue<Node> backSearch;
int fstep = , bstep = ;
frontSearch.push(start);
backSearch.push(finish);
Node current;
while (!frontSearch.empty() || !backSearch.empty())
{
int frontSize = (int) frontSearch.size();
while (frontSize--) // 直接将这一个队 全都 拿出来更新,就相当于上一中的step一样,控制搜索的层次
{
current = frontSearch.front();
frontSearch.pop(); for (int i = ; i < ; i++)
{
int fx = current.x + gx[i];
int fy = current.y + gy[i];
if (in_bound(fx, fy))
{
if (bvis[fx][fy] != -) // 如果 倒着搜 已经搜到了,返回
return fvis[current.x][current.y] + + bvis[fx][fy];
if (fvis[fx][fy] == -) //否则正着+1
{
Node temp;
temp.x = fx;
temp.y = fy;
fvis[fx][fy] = fvis[current.x][current.y] + ;
frontSearch.push(temp);
}
}
}
}
int backSize = (int) backSearch.size();
while (backSize--)
{
current = backSearch.front();
backSearch.pop(); for (int i = ; i < ; i++)
{
int fx = current.x + gx[i];
int fy = current.y + gy[i];
if (in_bound(fx, fy))
{
if (fvis[fx][fy] != -)
{
return bvis[current.x][current.y] + + fvis[fx][fy];
}
if (bvis[fx][fy] == -)
{
Node temp;
temp.x = fx;
temp.y = fy;
bvis[fx][fy] = bvis[current.x][current.y] + ;
backSearch.push(temp);
}
}
}
}
}
return -;
}
int main()
{
int test;
scanf("%d", &test);
while (test--)
{
scanf("%d", &n);
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
memset(fvis, -, sizeof(fvis));
memset(bvis, -, sizeof(bvis));
printf("%d\n", bfs());
}
return ;
}

双向bfs 方法二

 
05-06 03:21