dz 做企业网站,郑州网站建设郑州网站建设,学校网站系统破解版,长治网站建设培训文件P9425 [蓝桥杯 2023 国 B] AB 路线
题目描述
有一个由 N M N \times M NM 个方格组成的迷宫#xff0c;每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格#xff0c;目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。
由于特殊的原因#xf…P9425 [蓝桥杯 2023 国 B] AB 路线
题目描述
有一个由 N × M N \times M N×M 个方格组成的迷宫每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。
由于特殊的原因小蓝的路线必须先走 K K K 个 A 格子、再走 K K K 个 B 格子、再走 K K K 个 A 格子、再走 K K K 个 B 格子……如此反复交替。
请你计算小蓝最少需要走多少步才能到达右下角方格
注意路线经过的格子数不必一定是 K K K 的倍数即最后一段 A 或 B 的格子可以不满 K K K 个。起点保证是 A 格子。
例如 K 3 K 3 K3 时以下 3 3 3 种路线是合法的
AA
AAAB
AAABBBAAABBB以下 3 3 3 种路线不合法
ABABAB
ABBBAAABBB
AAABBBBBBAAA输入格式
第一行包含三个整数 N N N、 M M M 和 K K K。
以下 N N N 行每行包含 M M M 个字符A 或 B代表格子类型。
输出格式
一个整数代表最少步数。如果无法到达右下角输出 − 1 -1 −1。
输入输出样例 #1
输入 #1
4 4 2
AAAB
ABAB
BBAB
BAAA输出 #1
8说明/提示
样例说明
每一步方向如下下右下右上右下下路线序列 AABBAABBA。
评测用例规模与约定
对于 20 % 20\% 20% 的数据 1 ≤ N , M ≤ 4 1 \le N, M \le 4 1≤N,M≤4。对于另 20 % 20\% 20% 的数据 K 1 K 1 K1。对于 100 % 100\% 100% 的数据 1 ≤ N , M ≤ 1000 1 \le N, M \le 1000 1≤N,M≤1000 1 ≤ K ≤ 10 1 \le K \le 10 1≤K≤10。
第十四届蓝桥杯大赛软件赛决赛 C/C 大学 B 组 G 题
关键解题思路 状态定义 使用广度优先搜索(BFS)来寻找最短路径状态需要记录当前位置(x,y)、已走步数s、当前应该走的格子类型(flag)flag为false表示当前应该走A格子true表示当前应该走B格子 状态转移规则 每走一步步数s加1当步数s是K的倍数时需要切换格子类型(flag取反)下一步只能走到相邻的、与当前要求格子类型相同的格子 访问标记优化 使用四维数组vis[x][y][s%k][flag]来标记已访问状态只需要记录s对K取模的结果因为我们只关心当前是否需要切换格子类型 终止条件 当到达右下角(n,m)时返回已走步数s如果队列为空仍未到达终点则返回-1 特殊处理 起点保证是A格子所以初始flag为false最后一段A或B的格子可以不满K个这通过状态转移时检查当前格子类型实现
#include iostream
#include queue
#include cstring
using namespace std;
int n, m, k, ans 1000000, mv[4][2] {0, 1, 0, -1, 1, 0, -1, 0};
bool vis[1002][1002][12][2];
char a[1002][1002],c[2] {A, B};struct node {int x, y, s;bool flag;
};bool check(int x, int y, int s, bool flag) {return x 1 || y 1 || x n || y m || vis[x][y][s%k][flag] || c[flag] ! a[x][y];
}void bfs() {vis[1][1][0][false] true;queuenode q;q.push({1, 1, 0, false});while (!q.empty()) {node cur q.front();q.pop();int x cur.x, y cur.y, s cur.s;bool flag cur.flag;if (x n y m) {ans min(ans, s);return;}int next_s s 1;bool next_flag flag;if (next_s % k 0) {next_flag !flag;}for (int i 0; i 4; i) {int xi x mv[i][0], yi y mv[i][1];if (check(xi, yi, next_s, next_flag)) continue;vis[xi][yi][next_s%k][next_flag] true;q.push({xi, yi, next_s, next_flag});}}
}int main() {cin n m k;for (int i 1; i n; i) {for (int j 1; j m; j) {cin a[i][j];}}bfs();if (ans 1000000) cout -1;else cout ans;return 0;
}其实dfs也能做但是会超时
#includebits/stdc.h
using namespace std;
int n, m, k, ans 1e9, mv[4][2] {0, 1, 0, -1, 1, 0, -1, 0};
string s[1010];
bool vis[1010][1010][12][2];
char c[2] {A, B};bool check(int x, int y, int cnt, bool flag) {return x 0 || y 0 || x n || y m || vis[x][y][cnt%k][flag] || c[flag] ! s[x][y];
}void dfs(int x, int y, int cnt, bool flag) {if (x n-1 y m-1) {ans min(ans, cnt);return;}int next_cnt cnt 1;bool next_flag flag;if (next_cnt % k 0) {next_flag !flag;}for (int i 0; i 4; i) {int dx mv[i][0] x, dy mv[i][1] y;if (check(dx, dy, next_cnt, next_flag)) continue;vis[dx][dy][next_cnt%k][next_flag] true;dfs(dx, dy, next_cnt, next_flag);vis[dx][dy][next_cnt%k][next_flag] false;}
}int main() {cin n m k;for (int i 0; i n; i) {cin s[i];}vis[0][0][0][false] true;dfs(0, 0, 0, false);if (ans 1e9) cout -1;else cout ans;return 0;
}
