加载中…迷宫－－小学生编程竞赛题目（两种解法，一种简单的推荐）
(2016-09-18 19:13:53)
标签：
小学生程序竞赛c迷宫2014年第5题 |
分类： 其他 |
前两个月自己写了一个解法发到此博客里。今天把更简单的值得推荐的解法贴出来。一对比，就知道，当初我想得太复杂了。对于小学生学习编程而言，题目其实可以用更为简单的方式求解。
2016年9月18日写到：
（费了不少劲，写了几个版本，死了不少脑细胞。帮孩子做竞赛题目，我这个老妈也是蛮乒的。目前这个版本是最简单的，用了递归，貌似正确了。有喜欢的同学，可以用各种小于等于7*7的迷宫来测试一下。不知为何，这个网页貌似自动删除include后面的头文件，可能是尖括号的原因。一个头文件是fstream，一个头文件是string。）
试题 5 :迷宫(共 5 个测试点,每个点 4 分)
labyrinth.c / labyrinth.cpp / labyrinth.pas / labyrinth.bas
【问题描述】
鹏鹏在一个迷宫里困住了。
迷宫是长方形的,有 n 行 m 列个格子。一共有 3 类格子,空地用字符’.’ 表示,墙壁用’#’表示,陷阱用’*’表示。
特别地,迷宫中有两个特殊的格子:起点用’S’表示;终点用’E’表示。 起点和终点都是空地。(’S’和’E’均为大写字母)
鹏鹏的任务是:从起点出发,沿着某条路径,走到终点。
游戏对路径的要求有三条:每次只能向相邻格子(上/下/左/右)移动一步; 不能经过墙壁(即可以经过空地和陷阱);不能走出迷宫边界。
聪明的你请告诉鹏鹏,他能完成任务吗?如果能,鹏鹏能否不经过任何陷阱 就完成任务呢?
【输入文件】
文件名:labyrinth.in
文件中第一行为两个整数
n,m(2≤n,m≤7)。
接下来有 n 行,每行是一个长度为
m
的字符串,依次表示迷宫的每一行格子。
【输出文件】
文件名:labyrinth.out
文件仅有一行,是一个字符串。
如果鹏鹏可以不经过任何陷阱就到达终点,输出”GOOD”;否则,如果经过
若干陷阱能到达终点,输出”OK”;否则,输出”BAD”。(所有字母均为大写)
【样例输入 1】 34
##.E
S*.#
...*
【样例输出 1】 GOOD
【样例输入 2】 33
##E S*. #..
【样例输出 2】 OK
【样例解释】 ##67
1*5#
234*
样例 1 的最优路线为
1->2->3->4->5->6->7,如上图。
2016年11月19日，今天推荐简单优选解法（孩子在听完老师讲解后完成的，思路来自与老师：））。9月18日的那个版本放在后面，做个对比。
#include
#include
using namespace std;
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
char a[9][9];
int i,j,m,n;
bool flag,fl;
flag=true;
fl=false;
cin>>m;
cin>>n;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='S'){
a[i][j]='1';
}
}
}
while(flag){
flag=false;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(a[i][j]=='1'){
//cout<<i<<" "<<j<<endl;
//cout<<a[i+1][j]<<" "<<a[i-1][j]<<" " <<a[i][j+1]<<" "<<a[i][j-1]<<endl;
if((a[i+1][j]=='E')||(a[i-1][j]=='E')||(a[i][j+1]=='E')||(a[i][j-1]=='E')){
cout<<"GOOD"<<endl;
return 0;
}
else if(a[i+1][j]=='.'){
a[i+1][j]='1';
flag=true;
}
else if(a[i-1][j]=='.'){
a[i-1][j]='1';
flag=true;
}
else if(a[i][j+1]=='.'){
a[i][j+1]='1';
flag=true;
}
else if(a[i][j-1]=='.'){
a[i][j-1]='1';
flag=true;
}
else{
}
}
}
}
}
flag=true;
while(flag){
flag=false;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(a[i][j]=='1'){
if((a[i+1][j]=='E')||(a[i-1][j]=='E')||(a[i][j+1]=='E')||(a[i][j-1]=='E')){
cout<<"OK"<<endl;
return 0;
}
else if((a[i+1][j]=='.')||(a[i+1][j]=='*')){
a[i+1][j]='1';
flag=true;
}
else if((a[i-1][j]=='.')||(a[i-1][j]=='*')){
a[i-1][j]='1';
flag=true;
}
else if((a[i][j+1]=='.')||(a[i][j+1]=='*')){
a[i][j+1]='1';
flag=true;
}
else if((a[i][j-1]=='.')||(a[i][j-1]=='*')){
a[i][j-1]='1';
flag=true;
}
else{
}
}
}
}
}
cout<<"BAD"<<endl;
return 0;
}
（费了不少劲，写了几个版本，死了不少脑细胞。帮孩子做竞赛题目，我这个老妈也是蛮乒的。目前这个版本是最简单的，用了递归，貌似正确了。有喜欢的同学，可以用各种小于等于7*7的迷宫来测试一下。）
#include
#include
using namespace std;
ifstream cin("labyrinth.in");
ofstream cout("labyrinth.out");
int curhang,curlie,shang,slie,curdir,prehang,prelie;
char a[9][9];
int
int flag = 0;
typedef struct{
int hang;
int lie;
}HISTRY;
HISTRY his[100];
int hisidx=0;
int stardisflag = 0;
#define DEBUGFLAG 1
int retrieve(int h,int l)
{
int i;
int cnt=0;
for (i=0;i<=hisidx;i++)
{
if ((his[i].hang == h)&&(his[i].lie == l))
cnt++;
}
return cnt;
}
int onestep(int curhang, int curlie, int nexthang, int nextlie, int dir)
{
#if 1//DEBUGFLAG==1
cout<<"cur:"<<curhang<<' '<<curlie<<"==>> "<<nexthang<<' '<<nextlie<<endl;
#endif
if ((prehang!=curhang)||(prelie!=curlie))
{
his[hisidx].hang=curhang;
his[hisidx++].lie=curlie;
prehang = curhang;
prelie = curlie;
}
if ((flag == 2) || (retrieve(curhang,curlie) >= 10))
{
#if 1//DEBUGLFAG == 1
cout<<"h, l ="<<curhang<<" "<<curlie<<" "<<retrieve(curhang,curlie)<<"times"<<endl;
#endif
return 2;
}
if (a[nexthang][nextlie]=='E')
{
if (flag == 0)
return 0;
else
{
stardisflag = 1;
#if DEBUGFLAG==1
cout<<"stardisflag
#endif
flag = 0;
if(onestep(shang,slie,shang,slie+1,0)==0)
return 0;
else
return 1;
}
}
if
{
b[nexthang][nextlie]=dir;
return(onestep(nexthang,nextlie,nexthang,nextlie+1,0));
}
else if ((a[nexthang][nextlie]=='*') && (stardisflag == 0) && (b[curhang][curlie]!=((dir+2)%4)))
{
flag = 1;
b[nexthang][nextlie]=dir;
return(onestep(nexthang,nextlie,nexthang,nextlie+1,0));
}
else
{
if ((a[nexthang][nextlie]=='*') && (stardisflag == 1))
a[nexthang][nextlie]=='#';
if (dir == 0)
{
if (b[curhang][curlie]!=3)
return(onestep(curhang,curlie,curhang+1,curlie,1));
else
return(onestep(curhang,curlie,curhang,curlie-1,2));
}
else if (dir == 1)
{
if (b[curhang][curlie]!=0)
return(onestep(curhang,curlie,curhang,curlie-1,2));
else
return(onestep(curhang,curlie,curhang-1,curlie,3));
}
else if ((dir == 2) && (b[curhang][curlie]!=1))
return(onestep(curhang,curlie,curhang-1,curlie,3));
else
{
a[curhang][curlie]='#';
switch (b[curhang][curlie])
{
case 3:
return(onestep(curhang+1,curlie,curhang+1,curlie+1,0));
case 0:
return(onestep(curhang,curlie-1,curhang+1,curlie-1,1));
case 1:
return(onestep(curhang-1,curlie,curhang-1,curlie+1,0));
case 2:
return(onestep(curhang,curlie+1,curhang,curlie+2,0));
default:
flag = 2;
return 2;
}
}
}
}
int main(int argc,char**argv) {
int i,j,res;
int nn,m;
char x;
int
cin>>nn;
cin>>m;
cout<<"nn="<<nn<<"
"<<"m="<<m<<endl;
for (i=0;i<=nn+1;i++)
{
for (j=0;j<=m+1;j++)
a[i][j] = '#';
}
for (i=1;i<=nn;i++)
{
for (j=1;j<=m;j++)
{
cin>>a[i][j];
if (a[i][j] == 'S')
{
curhang = i;
curlie = j;
shang = i;
slie = j;
b[i][j] = 5;
}
}
}
res = onestep(curhang, curlie, curhang, curlie+1, 0);
if (res == 0)
cout << "GOOD" <<endl;
else if (res == 1)
cout << "OK" <<endl;
else
cout << "BAD" <<endl;
return(0);
}
喜欢
0
赠金笔