hdu1195 Open the Lock--单向BFS & 双向BFS

原题链接： ​​ http://acm.hdu.edu.cn/showproblem.php?pid=1195​​

一：题意

两个四位数的数字，经过一下三种方式变换，求出变成另一个数字的最小时间。

加1；减1；相邻交换

其中9+1变成1，1-1变成9，最左边与最右边不算相邻。

二：分析

 双向BFS，就是从两个点寻找一个共同的中间点。
然后把各自到这个中间点的步数加起来，及为最短步数。

单向BFS：

双向BFS：

 发现了不？
尤其是随着搜索广度的增大，那个范围是相当大啊！
双向BFS做法其实不难，两个队列。

三：AC代码

单向BFS：

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

#include <algorithm>
#include <iostream>
#include<string.h>
#include <queue>

using namespace std;

struct Node
{
  int num[4];
  int step;
  bool operator==(Node & node) const
  {
    for (int i = 0; i < 4; i++)
      if (num[i] != node.num[i])
        return 0;
    return 1;
  }
};

Node first, last;
int visited[11][11][11][11];

void bfs()
{
  int i;
  Node cur, t;
  queue<Node> q;

  cur = first;
  cur.step = 0;
  q.push(cur);
  visited[cur.num[0]][cur.num[1]][cur.num[2]][cur.num[3]] = 1;

  while (!q.empty())
  {
    cur = q.front();
    q.pop();
    if (cur == last)
    {
      printf("%d\n", cur.step);
      return;
    }

    for (i = 0; i < 4; i++) //+1  
    {
      t = cur;
      t.num[i]++;
      if (t.num[i] == 10)
        t.num[i] = 1;
      if (!visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
      {
        visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
        t.step++;
        q.push(t);
      }
    }
    for (i = 0; i < 4; i++) //-1  
    {
      t = cur;
      t.num[i]--;
      if (t.num[i] == 0)
        t.num[i] = 9;
      if (!visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
      {
        visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
        t.step++;
        q.push(t);
      }
    }
    for (i = 0; i < 3; i++) //交换  
    {
      t = cur;
      t.num[i] = cur.num[i + 1];
      t.num[i + 1] = cur.num[i];
      if (!visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]])
      {
        visited[t.num[0]][t.num[1]][t.num[2]][t.num[3]] = 1;
        t.step++;
        q.push(t);
      }
    }
  }
}



int main()
{
  int i, j, t;
  char s1[10], s2[10];
  scanf("%d", &t);
  while (t--)
  {
    scanf("%s%s", s1, s2);
    for (i = 0; i < 4; i++)
    {
      first.num[i] = s1[i] - '0';
      last.num[i] = s2[i] - '0';
    }
    memset(visited, 0, sizeof(visited));
    bfs();
  }


  return 0;
}

双向BFS：

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node
{
  int a[4], step;
};
int v1[10][10][10][10], v2[10][10][10][10];
node ft, lt;
void bbfs()
{
  int i, k, temp1, temp2;
  node  qf, ql, pf, pl;
  queue<node>  Q1, Q2;
  ft.step = 0; pf = ft;
  lt.step = 0; pl = lt;
  memset(v1, -1, sizeof(v1));
  memset(v2, -1, sizeof(v2));
  v1[pf.a[0]][pf.a[1]][pf.a[2]][pf.a[3]] = 0;
  v2[pl.a[0]][pl.a[1]][pl.a[2]][pl.a[3]] = 0;
  Q1.push(pf), Q2.push(pl);
  temp1 = temp2 = 0;
  while (1)
  {
    while (!Q1.empty() && Q1.front().step == temp1)//正搜,可能队列前面排着存在几个step和temp1相同的值
    {
      pf = Q1.front(); Q1.pop();
      if ((k = v2[pf.a[0]][pf.a[1]][pf.a[2]][pf.a[3]]) != -1)//判断是否反搜过
      {
        printf("%d\n", pf.step + k);
        return;
      }
      for (i = 0; i < 4; i++)//+1;
      {
        qf = pf;
        if (pf.a[i] == 9) qf.a[i] = 1;
        else qf.a[i] = pf.a[i] + 1;
        qf.step = pf.step + 1;
        if ((k = v2[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]]) != -1)//判断是否反搜过
        {
          printf("%d\n", qf.step + k);
          return;
        }
        if (v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] == -1)
        {
          v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] = qf.step;
          Q1.push(qf);
        }
      }
      for (i = 0; i < 4; i++)//-1;
      {
        qf = pf;
        if (pf.a[i] == 1) qf.a[i] = 9;
        else qf.a[i] = pf.a[i] - 1;
        qf.step = pf.step + 1;
        if ((k = v2[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]]) != -1)
        {
          printf("%d\n", qf.step + k);
          return;
        }
        if (v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] == -1)
        {
          v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] = qf.step;
          Q1.push(qf);
        }
      }
      for (i = 0; i < 3; i++)
      {
        qf = pf;
        qf.a[i] = pf.a[i + 1];
        qf.a[i + 1] = pf.a[i];
        qf.step = pf.step + 1;
        if ((k = v2[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]]) != -1)
        {
          printf("%d\n", qf.step + k);
          return;
        }
        if (v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] == -1)
        {
          v1[qf.a[0]][qf.a[1]][qf.a[2]][qf.a[3]] = qf.step;
          Q1.push(qf);
        }
      }
    }
    temp1 = Q1.front().step;

    while (!Q2.empty() && Q2.front().step == temp2)//反搜
    {
      pl = Q2.front(); Q2.pop();
      if ((k = v1[pl.a[0]][pl.a[1]][pl.a[2]][pl.a[3]]) != -1)
      {
        printf("%d\n", pl.step + k);
        return;
      }
      for (i = 0; i < 4; i++)//+1;
      {
        ql = pl;
        if (pl.a[i] == 9) ql.a[i] = 1;
        else ql.a[i] = pl.a[i] + 1;
        ql.step = pl.step + 1;
        if ((k = v1[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]]) != -1)
        {
          printf("%d\n", ql.step + k);
          return;
        }
        if (v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] == -1)
        {
          v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] = ql.step;
          Q2.push(ql);
        }
      }
      for (i = 0; i < 4; i++)//-1;
      {
        ql = pl;
        if (pl.a[i] == 1) ql.a[i] = 9;
        else ql.a[i] = pl.a[i] - 1;
        ql.step = pl.step + 1;
        if ((k = v1[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]]) != -1)
        {
          printf("%d\n", ql.step + k);
          return;
        }
        if (v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] == -1)
        {
          v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] = ql.step;
          Q2.push(ql);
        }
      }
      for (i = 0; i < 3; i++)//相邻交换
      {
        ql = pl;
        ql.a[i] = pl.a[i + 1];
        ql.a[i + 1] = pl.a[i];
        ql.step = pl.step + 1;
        if ((k = v1[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]]) != -1)
        {
          printf("%d\n", ql.step + k);
          return;
        }
        if (v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] == -1)
        {
          v2[ql.a[0]][ql.a[1]][ql.a[2]][ql.a[3]] = ql.step;
          Q2.push(ql);
        }
      }
    }
    temp2 = Q2.front().step;
  }
}
int main()
{
  int cas, i;
  char chf[5], chl[5];
  scanf("%d", &cas);
  while (cas--)
  {
    scanf("%s%s", chf, chl);
    for (i = 0; i < 4; i++)
    {
      ft.a[i] = chf[i] - '0';
      lt.a[i] = chl[i] - '0';
    }
    bbfs();
  }
  return 0;
}