Problem Description
说好了，题目不黑人。
给你一个8*8的矩阵，你的初始位置是左下角方格（用’U’表示），你的目标位置是右上角的方格(用’A’表示），其余的62个方格，如果是’.‘，表示这个方格为空，如果是’S’，表示这个方格有一块大石头。好了现在你开始从左下角出发，每次可以往上，下，左，右，左上，右上，左下，右下移动一个方格，或者你可以原地不动，一共九个动作方式，在你做完一个动作后，所有的大石头会往下掉一个方格（如果一个大石头的位置是（x，y）,那下一秒是（x+1，y）,不过如果它已经在最下面的一排了，那它就会掉出矩阵，不再出现），请注意，任一时刻，你不能和某一个大石头处在同一个方格，否则石头会把你XX掉。
现在的问题就是：你能从左下角安全抵达右上角么？ 如果能，输出“Yes”，反之，“No”。
Input
T->测试数据组数(T)。
对于每组数据，输入一个8*8的矩阵，其后有一空行。描述如上。
Output
对于第i组数据，请输出
Case #i: s(s是一个字符串，如果可以到达，则s为“Yes”，反之“No”)
Sample Input
2
.......A
........
........
........
........
........
........
U.......
.......A
........
........
........
........
.S......
S.......
US......
Sample Output
Case #1: Yes
Case #2: No
原题链接
解题思路
- 使用BFS遍历每个点所能移动的所有方向。
- 因为8步后所有石头都会掉出矩阵，所以BFS结束的条件就是U移动了8步【U→A最少7步（对角线），但要是有布局能让U移动7步到达A，通过BFS方式也一定会遍历到走8步的情况，不存在U→A仅有走7步的方案】。
- 设置一个变量记录当前移动的步数（即BFS层数），当步数增加时，需要执行落石操作。
经验总结
- C语言实现队列不知道长度时，使用链队（算法笔记p251队列&循环队列&链队）。
- 依照题目的意思，U是可以无限回头的，理论上不应该设置数字来记录是否已访问，但不设置的话Codeup一直报内存超限。
代码实现（C）
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
char matrix[8][8]; // 矩阵
bool inq[8][8]; // 记录该点是否被访问过
// 移动方向
int X[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
int Y[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
// 位置结点
typedef struct node {
int x;
int y;
int step; // 记录走到当前位置所需步数
struct node *next;
} node;
// 链队
typedef struct Queue {
node *front; // 队头指针
node *rear; // 队尾指针
} Queue;
// 初始化队列
void init(Queue *q) {
q->front = q->rear = NULL;
}
// 判断队列是否为空
bool isEmpty(Queue *q) {
return q->front == NULL;
}
// 入队
void enqueue(Queue *q, int x, int y, int step) {
node *newNode = (node *) malloc(sizeof(node));
newNode->x = x;
newNode->y = y;
newNode->step = step;
newNode->next = NULL;
inq[x][y] = true; // 更新入队标志
if (isEmpty(q))
q->front = q->rear = newNode;
else {
q->rear->next = newNode;
q->rear = newNode;
}
}
// 出队
void dequeue(Queue *q) {
if (isEmpty(q))
return; // 队列为空,无法出队
node *temp = q->front;
q->front = q->front->next;
free(temp);
if (q->front == NULL)
q->rear = NULL; // 队列已空,重置rear
}
// 获取队首元素
node getFront(Queue *q) {
node n;
if (isEmpty(q)) {
n.x = -1;
n.y = -1;
n.step = -1;
}
n.x = q->front->x;
n.y = q->front->y;
n.step = q->front->step;
return n;
}
void inputMatrix() {
getchar(); // 吸收T后的换行符或矩阵间的换行符
for (int j = 0; j < 8; ++j) {
for (int k = 0; k < 8; ++k)
scanf("%c", &matrix[j][k]);
getchar(); // 吸收矩阵每行结束后的换行符
}
memset(inq, false, sizeof(inq)); // 重置入队标志
}
void moveS() {
// 从后往前复制前一行的石头
for (int i = 7; i >= 0; --i)
for (int j = 7; j >= 0; --j) {
if (matrix[i][j] == 'S') {
matrix[i][j] = '.';
if (i < 7)
matrix[i + 1][j] = 'S';
}
}
}
// 判断要移动的位置是否符合要求
bool judgeNew(int x, int y) {
if (x >= 8 || y >= 8 || x < 0 || y < 0) // 越界
return false;
if (matrix[x][y] == 'S' || matrix[x - 1][y] == 'S') // 访问点是S或是S的落点
return false;
if (inq[x][y]) // 该点已访问过
return false;
return true;
}
Queue q;
bool BFS() {
init(&q);
enqueue(&q, 7, 0, 0);
int nowStep = 0; // 记录当前走了多少步
while (!isEmpty(&q)) {
node top = getFront(&q);
dequeue(&q);
if (nowStep != top.step) {
nowStep = top.step;
if (nowStep == 8) // 能走八步一定能走到A点
return true;
moveS();
}
for (int i = 0; i < 9; ++i) { // 遍历移动到各个方向的情况
int newX = top.x + X[i];
int newY = top.y + Y[i];
if (i == 8) // 原地不动时,需要设置当前位置未访问
inq[top.x][top.y] = false;
if (judgeNew(newX, newY)) // 能移动则将该位置入队
enqueue(&q, newX, newY, top.step + 1);
}
}
return false;
}
int main() {
int T;
while (~scanf("%d", &T)) {
for (int i = 1; i <= T; ++i) {
inputMatrix();
printf("Case #%d: %s\n", i, BFS() ? "Yes" : "No");
}
}
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看