hdu1254 推箱子--BFS

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

一：分析

分两步，一是箱子走到终点，二是人得走到箱子的前一个位置。

先是bfs_box在 t 点找到一个可行点tt，进而用bfs_people判断ps能否到达pd点。

二：AC代码

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;

int n, m, t;
int dir[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };

struct Node
{
  int x, y;
  int step;
  int mmap[10][10];
  bool cheak()
  {
    if (x >= 0 && x < n&&y >= 0 && y < m)
      return true;
    return false;
  }
};

Node pd;//人的目标
Node ss;
Node ps;//人的起点

/* 搜索人是否能到达指定位置 */
bool bfs_people(Node p)
{
  queue<Node> Q;
  ps = p;
  bool flag[10][10];
  memset(flag, 0, sizeof(flag));

  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      if (ps.mmap[i][j] == 4)//找到人的起点
      {
        ps.x = i;
        ps.y = j;
      }

  if (ps.x == pd.x&&ps.y == pd.y)//pd是人的目标位置
    return true;

  Q.push(ps);
  flag[ps.x][ps.y] = 1;

  while (!Q.empty())
  {
    Node t = Q.front();
    Q.pop();

    for (int i = 0; i < 4; i++)
    {
      Node tt = t;
      tt.x += dir[i][0];
      tt.y += dir[i][1];

      if (tt.cheak() && flag[tt.x][tt.y] == 0 && p.mmap[tt.x][tt.y] != 1 && p.mmap[tt.x][tt.y] != 2)
      {
        flag[tt.x][tt.y] = 1;
        if (tt.x == pd.x&&tt.y == pd.y)
          return true;
        Q.push(tt);
      }
    }
  }

  return 0;
}

/* 搜索箱子 */
int bfs_box()
{
  int flag[10][10][4];
  queue<Node> Q;
  Node t, tt;

  Q.push(ss);
  memset(flag, 0, sizeof(flag));

  while (!Q.empty())
  {
    t = Q.front();
    Q.pop();

    for (int i = 0; i < 4; i++)
    {
      tt = t;
      tt.x += dir[i][0];
      tt.y += dir[i][1];
      tt.step++;

      if (tt.cheak() && ss.mmap[tt.x][tt.y] != 1 && flag[tt.x][tt.y][i] == false)
      {
        pd.x = t.x - dir[i][0];//bfs_pepple（）的目标位置
        pd.y = t.y - dir[i][1];
        if (pd.cheak() == 0)
          continue;

        if (bfs_people(tt))
        {
          //更新地图，箱子和人的位置
          swap(tt.mmap[tt.x][tt.y], tt.mmap[t.x][t.y]);
          swap(tt.mmap[pd.x][pd.y], tt.mmap[ps.x][ps.y]);
          flag[tt.x][tt.y][i] = 1;
          if (ss.mmap[tt.x][tt.y] == 3)
            return tt.step;
          Q.push(tt);
        }
      }
    }
  }

  return -1;
}

int main()
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        scanf("%d", &ss.mmap[i][j]);
        if (ss.mmap[i][j] == 2)
        {
          ss.x = i;
          ss.y = j;
          ss.step = 0;
        }
      }
    }

    printf("%d\n", bfs_box());
  }

  return 0;
}