hdu 2102 A计划

2022-09-06 11:20:23

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=2102

A计划

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

双层bfs。。

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<map>

 using std::cin;

 using std::cout;

 using std::endl;

 using std::find;

 using std::sort;

 using std::map;

 using std::pair;

 using std::queue;

 using std::vector;

 using std::multimap;

 #define pb(e) push_back(e)

 #define sz(c) (int)(c).size()

 #define mp(a, b) make_pair(a, b)

 #define all(c) (c).begin(), (c).end()

 #define iter(c) decltype((c).begin())

 #define cls(arr,val) memset(arr,val,sizeof(arr))

 #define cpresent(c, e) (find(all(c), (e)) != (c).end())

 #define rep(i, n) for (int i = 0; i < (int)(n); i++)

 #define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)

 const int N = ;

 typedef unsigned long long ull;

 bool vis[][N][N];

 char G[][N][N];

 int H, W, T;

 const int dx[] = { , , -,  }, dy[] = { -, , ,  };

 struct Node {

     int c, x, y, s;

     Node(int i = , int j = , int k = , int l = ) :c(i), x(j), y(k), s(l) {}

 };

 bool bfs() {

     cls(vis, false);

     queue<Node> q;

     q.push(Node());

     vis[][][] = true;

     while (!q.empty()) {

         Node t = q.front(); q.pop();

         if (G[t.c][t.x][t.y] == 'P') return t.s <= T;

         rep(i, ) {

             int nx = t.x + dx[i], ny = t.y + dy[i];

             char &ch = G[t.c][nx][ny];

             if (nx <  || nx >= H || ny <  || ny >= W ) continue;

             if (ch == '*' || vis[t.c][nx][ny]) continue;

             if (ch == '#') {

                 if (G[t.c ^ ][nx][ny] == '#' || G[t.c ^ ][nx][ny] == '*') continue;

                 if (vis[t.c ^ ][nx][ny]) continue;

                 q.push(Node(t.c ^ , nx, ny, t.s + ));

                 vis[t.c ^ ][nx][ny] = vis[t.c][nx][ny] = true;

                 continue;

             }

             q.push(Node(t.c, nx, ny, t.s + ));

             vis[t.c][nx][ny] = true;

         }

     }

     return false;

 }

 inline void input(bool d) {

     rep(i, H) scanf("%s", G[d][i]);

 }

 int main() {

 #ifdef LOCAL

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w+", stdout);

 #endif

     int t;

     scanf("%d", &t);

     while (t--) {

         scanf("%d %d %d", &H, &W, &T);

         input(), input();

         puts(bfs() ? "YES" : "NO");

     }

     return ;

 }

码农公寓