重写 poj3083

时间：2010-07-01 来源：chhaya

杯具，以前做的一点都看不懂了，乱七八糟一坨还那么多代码。 http://blog.chinaunix.net/u3/102624/showart_2023765.html 最近重新写了一下，对这种搜索也更清楚了。0ms,200多k，比以前的改进好多啊。就是非递归的dfs写起来麻烦些.

#include <stdio.h>
#include <string.h>
#define N 50
struct point
{
  int x, y;
  int dir; //方向：上右下左分别是0 1 2 3
  int step; //dfs的时候用此来计数找了几个方向了
}start, end;
struct point dir[2][4] = {{{-1, 0, 0, 0}, {0, -1, 0, 0}, {1, 0, 0, 0}, {0, 1, 0, 0}},
{{1, 0, 0, 0}, {0, -1, 0, 0}, {-1, 0, 0, 0}, {0, 1, 0, 0}}};
char g[N][N];
int step;
int cur_dir;
struct point queue[N*N], stack[N*N], tmp_pos, cur_pos;
int mark[N][N];

int place(int w, int h, struct point p)
{
  if(p.x < 0 || p.x >= w || p.y < 0 || p.y >= h || g[p.y][p.x] == '#')
    return 0;
  return 1;
}

int dfs(int h, int w, int how)
{
  int top = 0, i;
  start.dir = -1;
  start.step = 1;
  stack[top++] = start;
  while (top > 0)
  {
    cur_pos = stack[top-1];
    for (i=(cur_pos.dir+1)%4, cur_pos.step; cur_pos.step<=4; i=(i+1)%4, cur_pos.step++)
    {
      tmp_pos.x = cur_pos.x + dir[how][i].x;
      tmp_pos.y = cur_pos.y + dir[how][i].y;
      if(place(w, h, tmp_pos))
      {
        break;
      }
    }
    stack[top-1].step = cur_pos.step;
    if(cur_pos.step<=4)
    {
      step++;
      if(tmp_pos.x == end.x && tmp_pos.y == end.y)
        return step;
      stack[top-1].dir = i;
      tmp_pos.dir = (i+6) % 4;
      tmp_pos.step = 1;
      stack[top++] = tmp_pos;
    }
    else
    {
      step++;
      top--;
    }
  }
  return step;
}

int bfs(int w, int h)
{
  int rear, head;
  int i;
  mark[start.y][start.x] = 1;
  head = rear = 0;
  queue[head++] = start;
  while(head > rear)
  {
    cur_pos = queue[rear++];
    for(i=0; i<4; i++)
    {
      tmp_pos.x = cur_pos.x + dir[0][i].x;
      tmp_pos.y = cur_pos.y + dir[0][i].y;
      if(place(w, h, tmp_pos) && mark[tmp_pos.y][tmp_pos.x] == 0)
      {
        tmp_pos.step = cur_pos.step + 1;
        if(tmp_pos.x == end.x && tmp_pos.y == end.y)
          return tmp_pos.step;
        queue[head++] = tmp_pos;
        mark[tmp_pos.y][tmp_pos.x] = 1;
      }
    }
  }
  return step;
}

int main()
{
  int w, h, n, i, j, k;
  scanf("%d", &n);
  for(k=0; k<n; k++)
  {
    scanf("%d %d", &w, &h);
    for(i=0; i<h; i++)
      for(j=0; j<w; j++)
      {
        scanf(" %c", &g[i][j]);
        if(g[i][j] == 'S')
        { start.x = j; start.y = i; }
        if(g[i][j] == 'E')
        { end.x = j; end.y = i; }
      }
    //左优先
    step = 1;
    dfs(h, w, 0);
    printf("%d", step);
    //右优先
    step = 1;
    dfs(h, w, 1);
    printf(" %d", step);
    //最短
    memset(mark, 0, sizeof(mark));
    printf(" %d\n", bfs(w, h));
  }
  return 0;

}