hdu1240 Asteroids!--DFS & BFS

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

一：题意

三维空间，中o表示可以走，x表示不能走，给出行走的起始点和目的点的坐标，问最少多少步可以从起点到达目的点。

二：AC代码

DFS：

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

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

int dirx[6] = { 1,-1,0,0,0,0 };
int diry[6] = { 0,0,1,-1,0,0 };
int dirz[6] = { 0,0,0,0,1,-1 };

char ch[11][11][11];
int dis[11][11][11];
int sx, sy, sz;
int dx, dy, dz;
int minn;
int n;

void dfs(int x, int y, int z, int cnt)
{
  if (x < 0 || y < 0 || z < 0 || x >= n || y >= n || z >= n)
    return;
  if (ch[z][x][y] == 'X')
    return;
  if (x == dx&&y == dy&&z == dz)
  {
    if (cnt < minn)
      minn = cnt;
    return;
  }
  if (cnt > dis[z][x][y])
    return;
  else
    dis[z][x][y] = cnt;

  int tx, ty, tz;
  for (int i = 0; i < 6; i++)
  {
    tx = x + dirx[i];
    ty = y + diry[i];
    tz = z + dirz[i];
    dfs(tx, ty, tz, cnt + 1);
  }
}

int main()
{
  char str[10];
  int i, j, k;

  while (~scanf("%s %d%*c", str, &n))
  {
    //getchar();
    for (k = 0; k < n; ++k)
    {
      for (i = 0; i < n; ++i)
      {
        for (j = 0; j < n; ++j)
        {
          ch[k][i][j] = getchar();
          dis[k][i][j] = 99999999;
        }
        getchar();
      }
    }

    scanf("%d %d %d", &sy, &sx, &sz);
    scanf("%d %d %d", &dy, &dx, &dz);
    scanf("%s", str);
    minn = 99999999;
    dfs(sx, sy, sz, 0);

    if (minn == 99999999)
      printf("NO ROUTE\n");
    else
      printf("%d %d\n", n, minn);
  }

  return 0;
}

BFS：

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <climits>

using namespace std;

const int MAX = 11;
const int INF = INT_MAX - 3;
const int dirx[6] = { 1,-1,0,0,0,0 }, diry[6] = { 0,0,1,-1,0,0 }, dirz[6] = { 0,0,0,0,1,-1 };

typedef struct Point {
  int x, y, z;
}Point;

char map[MAX][MAX][MAX];
int dist[MAX][MAX][MAX];
int sx, sy, sz, dx, dy, dz;
int minx, n;

Point pp;

queue<Point> que;

int bfs(int x, int y, int z) 
{
  pp.x = x;
  pp.y = y;
  pp.z = z;
  que.push(pp);
  int i, tx, ty, tz;
  while (!que.empty()) 
  {
    pp = que.front();
    x = pp.x;
    y = pp.y;
    z = pp.z;
    que.pop();
    if (x == dx && y == dy && z == dz)
      break;
    for (i = 0; i < 6; ++i) 
    {
      tx = x + dirx[i];
      ty = y + diry[i];
      tz = z + dirz[i];

      if (tx < 0 || ty < 0 || tz < 0 || tx >= n || ty >= n || tz >= n)continue;
      if (map[tz][tx][ty] == 'X')continue;
      if (dist[z][x][y] + 1 > dist[tz][tx][ty])continue;

      dist[tz][tx][ty] = dist[z][x][y] + 1;
      pp.x = tx;
      pp.y = ty;
      pp.z = tz;
      que.push(pp);
    }
  }
  return dist[dz][dx][dy];
}

int main() 
{
  char str[10];
  int i, j, k;
  while (scanf("%s %d%*c", str, &n) != EOF) 
  {
    for (k = 0; k < n; ++k) 
    {
      for (i = 0; i < n; ++i) 
      {
        for (j = 0; j < n; ++j) 
        {
          map[k][i][j] = getchar();
          dist[k][i][j] = 99999999;
        }
        getchar();
      }
    }

    scanf("%d %d %d", &sy, &sx, &sz);
    scanf("%d %d %d", &dy, &dx, &dz);
    scanf("%s", str);
    dist[sz][sx][sy] = 0;
    minx = bfs(sx, sy, sz);

    if (minx == 99999999) 
      printf("NO ROUTE\n");
    else 
      printf("%d %d\n", n, minx);
    
    while (!que.empty())
      que.pop();
  }
  return 0;
}