做网站资料准备什么,oss可以做视频网站吗,创建网站制作首页,新企业建网站目录 Problem DescriptionInputOutputSample InputSample Output原题链接解题思路经验总结代码实现#xff08;C#xff09; Problem Description
说好了#xff0c;题目不黑人。
给你一个8*8的矩阵#xff0c;你的初始位置是左下角方格#xff08;用’U’表示#xff… 目录 Problem DescriptionInputOutputSample InputSample Output原题链接解题思路经验总结代码实现C Problem Description
说好了题目不黑人。
给你一个8*8的矩阵你的初始位置是左下角方格用’U’表示你的目标位置是右上角的方格(用’A’表示其余的62个方格如果是’.‘表示这个方格为空如果是’S’表示这个方格有一块大石头。好了现在你开始从左下角出发每次可以往上下左右左上右上左下右下移动一个方格或者你可以原地不动一共九个动作方式在你做完一个动作后所有的大石头会往下掉一个方格如果一个大石头的位置是xy,那下一秒是x1y,不过如果它已经在最下面的一排了那它就会掉出矩阵不再出现请注意任一时刻你不能和某一个大石头处在同一个方格否则石头会把你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原题链接
Codeup_4054问题 B: DFS or BFS?
解题思路
使用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.hchar 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;
}
