真题解析│蓝桥杯省赛真题之迷宫、跳蚱蜢
-
-
梁老师 北京小升初老师～
0 人点赞了该文章 · 83 浏览
2017年蓝桥杯软件类省赛C++大学A组第1题“迷宫”、第2题“跳蚱蜢”，两道填空题。
迷宫
题目链接：
http://oj.ecustacm.cn/problem.php?id=1317
1. 投机取巧的搞法
#include<iostream>
using namespace std;
int main(){
cout << 31 << endl;
return 0;
}2. 还是用这题来练练DFS编码吧
题解：
一道搜索题，可以选择暴力dfs，代码简短
我写的稍微长一点，但可以确保每个点只走到一次，稍微优化了那么一丢丢
此题唯一的坑点是提交到OJ时，千万不要写输入！！
直接输出一个数字就好惹…
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
int mp[20][20];
int vis[20][20];
bool tag[200];
int cnt[200];
int X[] = {0, 0, 0, -1, 1};
int Y[] = {0, -1, 1, 0, 0};
void solve(int x, int y, int id)
{
while(x >= 1 && x <= 10 && y >= 1 && y <= 10 && !vis[x][y]){
vis[x][y] = id;
cnt[id]++;
int now = mp[x][y];
x += X[now];
y += Y[now];
}
if(x < 1 || x > 10 || y < 1 || y > 10){
tag[id] = true;
return ;
}
if(vis[x][y]){
if(tag[vis[x][y]]) tag[id] = true;
}
return ;
}
int main(){
for(int i = 1 ; i <= 10 ; i++){
string s; cin >> s;
for(int j = 0 ; j < 10 ; j++){
if(s[j] == 'L') mp[i][j + 1] = 1;
else if(s[j] == 'R') mp[i][j + 1] = 2;
else if(s[j] == 'U') mp[i][j + 1] = 3;
else if(s[j] == 'D') mp[i][j + 1] = 4;
}
}
int id = 1;
for(int i = 1 ; i <= 10 ; i++){
for(int j = 1 ; j <= 10 ; j++){
if(!vis[i][j]){
solve(i, j, id);
id++;
}
}
}
/*for(int i = 1 ; i <= 10 ; i++){
for(int j = 1 ; j <= 10 ; j++){
printf("%3.d",vis[i][j]);
}
cout << endl;
}*/
int res = 0;
for(int i = 1 ; i < id ; i++){
if(tag[i]) res += cnt[i];
}
printf("%d\n", res);
return 0;
}跳蚱蜢
题目链接：
http://oj.ecustacm.cn/problem.php?id=1318
又是一道填空题，能用手数出答案吗？
1. 建模
直接让蚱蜢跳到空盘有点麻烦，因为有很多蚱蜢在跳，跳晕了。如果看成空盘跳到蚱蜢的位置就简单多了，只有一个空盘在跳。
2. 判重
3.map判重
把9个数字的排列定义为一种状态，即字符串s，例如初始状态“012345678”是一个串。对应交换之后产生的s，我们可以使用map判重，将该字符串以及它首次出现的时间作为一个单位推入队列中，由于BFS的性质我们能看出，首次找到结果状态的时间t即是最小的答案。
倪文迪的代码：
#include<bits/stdc++.h>
using namespace std;
struct node
{
node(){}
node(string ss, int tt){
s = ss, t = tt;
}
string s;
int t;
};
map<string, bool> mp;
queue<node> q;
void solve()
{
while(!q.empty()){
node now = q.front();
q.pop();
string s = now.s; int t = now.t;
if(s == "087654321"){
cout << t << endl;
break;
}
int i;
for(i = 0 ; i < 10 ; i++){
if(s[i] == '0') break;
}
for(int j = i - 2 ; j <= i + 2 ; j++){
int k = (j + 9) % 9;
if(k == i) continue;
char tmp;
tmp = s[i];s[i] = s[k];s[k] = tmp;
if(!mp[s]){
mp[s] = true;
q.push(node(s, t + 1));
}
tmp = s[i];s[i] = s[k];s[k] = tmp;
}
}
}
int main(){
string s = "012345678";
q.push(node(s, 0));
mp[s] = true;
solve();
return 0;
}4. set判重
代码参考：
https://blog.csdn.net/crazymooo/article/details/108816699
5.康托判重
以上是截图。
下面是书中的代码，用“BFS + 康托(Cantor)”解决了八数码问题，其中BFS用STL的queue实现。
#include<bits/stdc++.h>
const int LEN = 362888; //状态共9!=362880种
using namespace std;
struct node{
int state[9]; //记录一个八数码的排列，即一个状态
int dis; //记录到起点的距离
};
int dir[4][2] = {{-1,0}, {0,-1},{1,0},{0,1}};
//左、上、右、下顺时针方向。左上角坐标是(0,0)
int visited[LEN]={0}; //与每个状态对应的记录，Cantor函数对它置数，并判重
int start[9]; //开始状态
int goal[9]; //目标状态
long int factory[] = {1,1,2,6,24,120,720,5040,40320,362880};
//Cantor用到的常数
bool Cantor(int str[], int n) { //用康托展开判重
long result = 0;
for(int i = 0; i < n; i++) {
int counted = 0;
for(int j = i+1; j < n; j++) {
if(str[i] > str[j]) //当前未出现的元素中是排在第几个
++counted;
}
result += counted*factory[n-i-1];
}
if(!visited[result]) { //没有被访问过
visited[result] = 1;
return 1;
}
else
return 0;
}
int bfs() {
node head;
memcpy(head.state, start, sizeof(head.state)); //复制起点的状态
head.dis = 0;
queue <node> q; //队列中放状态
Cantor(head.state, 9); //用康托展开判重，目的是对起点的visited[]赋初值
q.push(head); //第一个进队列的是起点状态
while(!q.empty()) { //处理队列
head = q.front();
q.pop(); //可在此处打印head.state，看弹出队列的情况
int z;
for(z = 0; z < 9; z++) //找这个状态中元素0的位置
if(head.state[z] == 0) //找到了
break;
//转化为二维，左上角是原点(0, 0)。
int x = z%3; //横坐标
int y = z/3; //纵坐标
for(int i = 0; i < 4; i++){ //上、下、左、右最多可能有4个新状态
int newx = x+dir[i][0]; //元素0转移后的新坐标
int newy = y+dir[i][1];
int nz = newx + 3*newy; //转化为一维
if(newx>=0 && newx<3 && newy>=0 && newy<3) {//未越界
node newnode;
memcpy(&newnode,&head,sizeof(struct node));//复制这新的状态
swap(newnode.state[z], newnode.state[nz]);//把0移动到新的位置
newnode.dis ++;
if(memcmp(newnode.state,goal,sizeof(goal)) == 0)
//与目标状态对比
return newnode.dis; //到达目标状态，返回距离，结束
if(Cantor(newnode.state, 9)) //用康托展开判重
q.push(newnode); //把新的状态放进队列
}
}
}
return -1; //没找到
}
int main(){
for(int i = 0; i < 9; i++) cin >> start[i]; //初始状态
for(int i = 0; i < 9; i++) cin >> goal[i]; //目标状态
int num = bfs();
if(num != -1) cout << num << endl;
else cout << "Impossible" << endl;
return 0;
}
添加 家长论坛微信
全部 0条评论