POJ1915Knight Moves（单向BFS + 双向BFS）

时间：2023-03-08 22:20:08

题目链接

单向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 方法二

 

相关文章