A50859. 迷宫把一个 n 行 m 列的字符阵列看做一个迷宫，迷宫仅包含 L、Q、B、S 中的大写字母（蓝桥杯赛的汉语拼音首字母）。初始时，你可以从任意一个“L”字母开始，移向相邻的“Q”字母，然后从此“Q”字母出发，移向相邻的“B”字母，然后从此“B”字母出发，移向相邻的“S”字母……。这样，你就算是走过了一个“LQBS”字符序列。接下来，仍然可以从此“S”字母出发，移向相邻的“L”字母……，重复上述的动…
填空题
困难
知识点
题目描述
迷宫
把一个 n 行 m 列的字符阵列看做一个迷宫，迷宫仅包含 L、Q、B、S 中的大写字母（蓝桥杯赛的汉语拼音首字母）。
初始时，你可以从任意一个“L”字母开始，移向相邻的“Q”字母，然后从此“Q”字母出发，移向相邻的“B”字母，然后从此“B”字母出发，移向相邻的“S”字母……。这样，你就算是走过了一个“LQBS”字符序列。
接下来，仍然可以从此“S”字母出发，移向相邻的“L”字母……，重复上述的动作，你就可以不断地走过“LQBS”序列。
请注意，所谓相邻仅包含上、下、左、右 4 个方向，且只能从 L->Q，从 Q->B，从 B->S，从 S->L。
可以想像，由于选择的出发点不同，我们有可能在迷宫中走过无数次的“LQBS”，或者是有限次的“LQBS”，
或者一次也走不了。
编程实现：
请你编写程序，求出在给定的迷宫中，我们最多可以走过多少次“LQBS”?
输入：
第一行：正整数 n,m，表示迷宫的规模为 n 行 m 列，0<m<100，0<n<100
接下来的 n 行：每行 m 个符合题意的字母，字母间无空格。
输出：
一个整数。即：如果在迷宫中可以无限次的走过“LQBS”，输出-1，否则，输出可以走过“LQBS”的最多次数。
样例 1 输入：
1 2
LQ样例 1 输出：
0样例 2 输入：
3 3
LSB
QBQ
BSL样例 2 输出：
-1样例 3 输入：
4 4
BLQB
BBQS
SBQL
QQQQ样例 3 输出：
2参考答案
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
const int N=110;
char g[N][N];
int f[N][N];
int n,m;
bool wuxian;
int mstep,step=1;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<0||xx>n-1||yy<0||yy>m-1)continue;//越界跳过
if((g[x][y]=='L' && g[xx][yy]=='Q')||(g[x][y]=='Q' && g[xx][yy]=='B')||
(g[x][y]=='B' && g[xx][yy]=='S')||(g[x][y]=='S' && g[xx][yy]=='L')){
if(f[xx][yy]){
wuxian=true;
return ;
}
f[xx][yy]=1;
step++;
mstep=max(mstep,step);
dfs(xx,yy);
f[xx][yy]=0;
step--;
}
}
return ;
}
int main()
{
//freopen("LQBS3.in","r",stdin);
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='L'){
memset(f,0,sizeof(f));
dfs(i,j);
}
if(wuxian){
cout<<-1<<endl;
return 0;
}
}
}
cout<<mstep/4<<endl;
return 0;
}答案解析
考察知识:
搜索与回朔
由于部分学员暂时未学到搜索与回朔算法,所以采用循环遍历类似穷举算法进行题解
上一题
下一题