Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题很郁闷...计划一小时之内...搞了三四小时。

Posted by vivian2086 at 2009-08-21 09:07:39 on Problem 2251
皆因两个问题!犯的错误是:
1 处理完一层结点后mid 应该指向队列的下一层结点的最后一个,也就是tail. 我却指向了下一层的第一个。
3 对某位置标志visited 要在放进队列前标志,而不是等到用head 从队列头取出才标志为visited. 后者会导致同一结点重复入列,内存畸形增长

#include <stdio.h>
#include <string.h>

struct map{			/* 三维节点坐标,队列用 */
  char d;
  char r;
  char c;
};

char dun[30][30][30];		/* 地图 */
int d, r, c;			/* 3D坐标界限 */

int dir[6][3] = {		/* 移动方向 */
  {1, 0, 0},
  {0, 0, -1},
  {0, -1, 0},
  {0, 0, 1},
  {0, 1, 0},
  {-1, 0, 0},
};

int bfs(int sd, int sr, int sc)
{
  struct map que[27000];	/* 队列 */
  int mid, head, tail, step, nd, nr, nc, i; /* head, tail 队列的和尾,当head==mid时,处理完一层节点 */
  memset(que, 0, sizeof(que));		    /* nd, nr, nc当前节点的相邻节点, next d, next r,next c*/
  step = mid = head = tail = 0;
  
  que[head].d = sd;		/* 初始化 */
  que[head].r = sr;
  que[head].c = sc;

  for (tail ; head <= tail; head++)
    {
     
      if(dun[que[head].d][que[head].r][que[head].c] == 'E')
	{
	  return step;
	}


      for (i = 0; i < 6; i++)
	{
	  nd = que[head].d + dir[i][0];
	  nr = que[head].r + dir[i][1];
	  nc = que[head].c + dir[i][2];
	  if (dun[nd][nr][nc] == '#' ||
	      nd < 0 || nd >= d || nr < 0 || nr >= r || nc < 0 || nc >= c)
	    {
	      continue;
	    }
	  if (dun[nd][nr][nc] == '.')
	    {
	      dun[nd][nr][nc] = '#';
	    }

	  tail++;	  
	  que[tail].d = nd;
	  que[tail].r = nr;
	  que[tail].c = nc;

	}
      if (mid == head)
	{
	  step++;
	  mid = tail;
	}
    }
  return 0;
}

main()
{
  int sd, sr, sc, i, j, k, sum;
  scanf("%d%d%d", &d, &r, &c);

  while (d)
    {
      memset(dun, 0, sizeof(dun));
      for (i=0; i<d; i++)
	{
	  for (j=0; j<r; j++)
	    {
	      scanf("%s", &dun[i][j]);
	    }
	}

      for (i=0; i<d; i++)
	{
	  for (j=0; j<r; j++)
	    {
	      for (k=0; k<c; k++)
		{
		  if (dun[i][j][k] == 'S')
		    {
		      sd = i, sr = j, sc = k;
		      goto here;
		    }
		}
	    }
	}
    here:
      sum = bfs(sd, sr, sc);
      if (sum)
	{
	  printf("Escaped in %d minute(s).\n", sum);
	}
      else
	{
	  printf("Trapped!\n");
	}
      scanf("%d%d%d", &d, &r, &c);      
    }
  return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator