HDU 2102 A計劃

Problem Description

可憐的公主在一次次被魔王擄走一次次被騎士們救回來之後，而今，不幸的她再一次面臨生命的考驗。魔王已經發出消息說将在T時刻吃掉公主，因為他聽信謠言說吃公主的肉也能長生不老。年邁的國王正是心急如焚，告招天下勇士來拯救公主。不過公主早已習以為常，她深信智勇的騎士LJ肯定能将她救出。

現據密探所報，公主被關在一個兩層的迷宮裡，迷宮的入口是S（0，0，0），公主的位置用P表示，時空傳輸機用#表示，牆用*表示，平地用.表示。騎士們一進入時空傳輸機就會被轉到另一層的相對位置，但如果被轉到的位置是牆的話，那騎士們就會被撞死。騎士們在一層中隻能前後左右移動，每移動一格花1時刻。層間的移動隻能通過時空傳輸機，且不需要任何時間。

Input

輸入的第一行C表示共有C個測試資料，每個測試資料的前一行有三個整數N，M，T。 N，M迷宮的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宮的第一層的布置情況，後N*M表示迷宮第二層的布置情況。

Output

如果騎士們能夠在T時刻能找到公主就輸出“YES”，否則輸出“NO”。

Sample Input

1

5 5 14

S*#*.

.#...

.....

****.

...#.

..*.P

#.*..

***..

...*.

*.#..

Sample Output

YES

簡單的廣搜

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 15;
int n, m, T, C, a[2][maxn][maxn], t[2][maxn][maxn], f[2][maxn][maxn];
int b[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
char s[maxn];

struct abc
{
  int x, y, z;
  abc(){}
  abc(int x, int y, int z) :x(x), y(y), z(z){}
};

void bfs(int x, int y, int z)
{
  memset(f, 0, sizeof(f));
  memset(t, -1, sizeof(t));
  queue<abc> p;
  abc q;
  p.push(abc(x, y, z));
  t[0][1][1] = 0;
  f[x][y][z] = 1;
  int flag = 0;
  while (!p.empty())
  {
    q = p.front(); p.pop();
    if (a[q.x][q.y][q.z] >= 2)
    {
      if (a[q.x][q.y][q.z] >= 3) { flag = 1; break; }
      if (!f[1 - q.x][q.y][q.z] && a[1 - q.x][q.y][q.z])
      {
        f[1 - q.x][q.y][q.z] = 1;
        t[1 - q.x][q.y][q.z] = t[q.x][q.y][q.z];
        p.push(abc(1 - q.x, q.y, q.z));
      }
    }
    else 
    for (int i = 0; i<4; i++)
      if (q.y + b[i]>0 && q.y + b[i] <= n)
        if (q.z + c[i]>0 && q.z + c[i] <= m)
          if (a[q.x][q.y + b[i]][q.z + c[i]])
            if (!f[q.x][q.y + b[i]][q.z + c[i]])
            {
              f[q.x][q.y + b[i]][q.z + c[i]] = 1;
              t[q.x][q.y + b[i]][q.z + c[i]] = t[q.x][q.y][q.z] + 1;
              p.push(abc(q.x, q.y + b[i], q.z + c[i]));
            }
  }
  if (flag&&t[q.x][q.y][q.z] <= T) printf("YES\n");
  else printf("NO\n");
}

int main()
{
  scanf("%d", &C);
  while (C--)
  {
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < n + n; i++)
    {
      scanf("%s", s);
      for (int j = 1; j <= m; j++)
      {
        switch (s[j - 1]){
          case 'S':a[i / n][i % n + 1][j] = 1; break;
          case '.':a[i / n][i % n + 1][j] = 1; break;
          case '*':a[i / n][i % n + 1][j] = 0; break;
          case '#':a[i / n][i % n + 1][j] = 2; break;
          case 'P':a[i / n][i % n + 1][j] = 3; break;
        }
      }
    }
    bfs(0, 1, 1);
  }
  return 0;
}