问题 B: DFS or BFS?

xiaoxiao2021-03-01  20

 

问题 B: DFS or BFS?

时间限制: 1 Sec  内存限制: 128 MB

题目描述

说好了,题目不黑人。

给你一个8*8的矩阵,你的初始位置是左下角方格(用'U’表示),你的目标位置是右上角的方格(用'A'表示),其余的62个方格,如果是'.',表示这个方格为空,如果是'S',表示这个方格有一块大石头。好了现在你开始从左下角出发,每次可以往上,下,左,右,左上,右上,左下,右下移动一个方格,或者你可以原地不动,一共九个动作方式,在你做完一个动作后,所有的大石头会往下掉一个方格(如果一个大石头的位置是(x,y),那下一秒是(x+1,y),不过如果它已经在最下面的一排了,那它就会掉出矩阵,不再出现),请注意,任一时刻,你不能和某一个大石头处在同一个方格,否则石头会把你XX掉。

现在的问题就是:你能从左下角安全抵达右上角么? 如果能,输出“Yes”,反之,“No”。

输入

T->测试数据组数(T)。

对于每组数据,输入一个8*8的矩阵,其后有一空行。描述如上。

输出

对于第i组数据,请输出

Case #i: s(s是一个字符串,如果可以到达,则s为“Yes”,反之“No”)

样例输入

2 .......A ........ ........ ........ ........ ........ ........ U....... .......A ........ ........ ........ ........ .S...... S....... US......

样例输出

Case #1: Yes Case #2: No

方法一:深度优先遍历

#include <iostream> #include <string> #include <algorithm> using namespace std; struct Node { int x, y; }; char mix[8][8]; bool storeIndex[16][8], moveIndex[8][8], tempIndex = false; int dx[9] = {-1, 0, -1, 1, 0, -1, 1, 1, 0}, dy[9] = {0, 1, 1, 0, -1, -1, -1, 1, 0}; void moveStore() { int i, j; for (i = 14; i >= 0; i--) { for (j = 0; j < 8; j++) { if (storeIndex[i][j]) { storeIndex[i][j] = false; storeIndex[i + 1][j] = true; } } } } void unmoveStore() { int i, j; for (i = 1; i < 16; i++) { for (j = 0; j < 8; j++) { if (storeIndex[i][j]) { storeIndex[i][j] = false; storeIndex[i - 1][j] = true; } } } } bool check(Node temp) { if (temp.x < 0 || temp.x > 7 || temp.y < 0 || temp.y > 7) { return false; } if (storeIndex[temp.x][temp.y]) //有石头 { return false; } if (moveIndex[temp.x][temp.y]) { return false; } return true; } bool dfs(Node node) { Node temp; if (tempIndex) { return false; } if (node.x == 0 && node.y == 7) { return true; } if (storeIndex[node.x][node.y]) { return false; } for (int i = 0; i < 9; i++) { temp.x = node.x + dx[i]; temp.y = node.y + dy[i]; if (check(temp)) { //移动石头 moveIndex[node.x][node.y] = true; moveStore(); if (dfs(temp)) { return true; } unmoveStore(); moveIndex[node.x][node.y] = false; } } return false; } void getMthrix() { int i, j; string temp; for (i = 0; i < 8; i++) { getline(cin, temp); if (temp == "SSSSSSSS") { tempIndex = true; } for (j = 0; j < 8; j++) { mix[i][j] = temp[j]; moveIndex[i][j] = false; if (mix[i][j] == 'S') { storeIndex[i][j] = true; } else { storeIndex[i][j] = false; } } } getline(cin, temp); } int main() { int t, i; Node temp; bool res; while (cin >> t) { cin.ignore(); for (i = 0; i < t; i++) { tempIndex = false; getMthrix(); temp.x = 7, temp.y = 0; cout << "Case #" << (i + 1) << ":"; res = dfs(temp); if (res) { cout << " Yes" << endl; } else { cout << " No" << endl; } } } return 0; } /************************************************************** Problem: 4054 User: morizunzhu Language: C++ Result: 正确 Time:0 ms Memory:2020 kb ****************************************************************/

 

转载请注明原文地址: https://www.6miu.com/read-3349958.html

最新回复(0)