poj 3322 Bloxorz I [bfs]

解题思路

题意：

要把x所在地方的盒子翻滚到O处，最少需要的滚动次数。

思路：

不算很难的bfs吧，可是做了很久，主要是一开始状态搞多了，其实只有三个：站立，横躺和竖躺的，每个点只要记录x,y坐标，状态，走了多少步就行了。当盒子躺着时，只记录上面（或者左边）那个。当状态处于站立，坐标所在位置是O就到了。

源程序

#include <stdio.h>
#include <string.h>
#define N 503
int w, h;
char g[N][N];
enum stat{stand=1, vert, hori}; //立，竖，横

struct str
{
  int x, y;
  enum stat how;
  int step;
}start, queue[10000000];
int mark[N][N][4];
int mov[3][4][3] = { {{1, 0, -2}, {2, 1, 0}, {1, 0, 1}, {2, -2, 0}}, //stand 上右下左，（状态，x，y）

                     {{-1, 0, -1}, {0, 1, 0}, {-1, 0, 2}, {0, -1, 0}}, //vert

                     {{0, 0, -1}, {-2, 2, 0}, {0, 0, 1}, {-2, -1, 0}} //hori

                   };

/*
  return 0: 不可放
         1：可放
         2：到达终点
*/
int place(struct str *tmp)
{
  if(tmp->x >= 0 && tmp->y >= 0 && tmp->x < w && tmp->y < h)
  {
    if(tmp->how == stand) //站立时，不能是#或者E

    {
      if(g[tmp->y][tmp->x] == 'O')
        return 2;
      if(mark[tmp->y][tmp->x][tmp->how] || g[tmp->y][tmp->x] == '#' || g[tmp->y][tmp->x] == 'E')
        return 0;
    }
    if(tmp->how == vert) //躺着时，不能有一个是#或者O

      if(mark[tmp->y][tmp->x][tmp->how] || tmp->y+1 >= h
         || g[tmp->y][tmp->x] == '#' || g[tmp->y+1][tmp->x] == '#'
         || g[tmp->y][tmp->x] == 'O' || g[tmp->y+1][tmp->x] == 'O' )
        return 0;
    if(tmp->how == hori)
      if(mark[tmp->y][tmp->x][tmp->how] || tmp->x+1 >= w
         || g[tmp->y][tmp->x] == '#' || g[tmp->y][tmp->x+1] == '#'
         || g[tmp->y][tmp->x] == 'O' || g[tmp->y][tmp->x+1] == 'O')
        return 0;
    return 1;
  }
  return 0;
}

int bfs()
{
  int front, rear, i, ok;
  struct str tmp, cur;
  mark[start.y][start.x][start.how] = 1;
  front = rear = 0;
  start.step = 0;
  queue[front++] = start;

  while(rear < front)
  {
    cur = queue[rear++];
    for(i=0; i<4; i++)
    {
      tmp.x = cur.x + mov[cur.how-1][i][1];
      tmp.y = cur.y + mov[cur.how-1][i][2];
      tmp.how = cur.how + mov[cur.how-1][i][0];
      ok = place(&tmp);
      if(ok == 2) //到达

        return cur.step+1;
      if(ok == 1) //放入队列

      {
        mark[tmp.y][tmp.x][tmp.how] = 1;
        tmp.step = cur.step + 1;
        queue[front++] = tmp;
      }
    }
  }
  return -1;
}

int main()
{
  int ret;
  int i, j;
  char a;
  freopen("3322.in", "r", stdin);
  while (1)
  {
    scanf("%d%d", &h, &w);
    if(h == 0 && w == 0)
      break;
    start.how = 0;
    for (i=0; i<h; i++)
    {
      for (j=0; j<w; j++)
      {
        scanf(" %c", &a);
        g[i][j] = a;

        if (a == 'X')
        {
          if(start.how == stand)
          {
            if(start.x == j)
              start.how = vert;
            else
              start.how = hori;
          }
          else
          {
            start.x = j;
            start.y = i;
            start.how = stand;
          }
        }
      }
    }
    memset(mark, 0, sizeof(mark));
    ret = bfs();
    if(ret == -1)
      printf("Impossible\n");
    else
      printf("%d\n", ret);
  }//while

  return 0;
}