[蓝桥杯2017初赛]迷宫 DFS

题目描述

X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,R表示走到右边的房间,U表示走到上坡方向的房间,D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此!
开始的时候,直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
迷宫地图如下:
------------
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
------------
请你计算一下,最后,有多少玩家会走出迷宫? 而不是在里边兜圈子。

输出

输出一个整数表示答案
 

提示

为方便理解,可参考此图文章来源地址:https://www.yii666.com/article/754241.html

[蓝桥杯2017初赛]迷宫 DFS网址:yii666.com<

答案:31

DFS:文章来源地址https://www.yii666.com/article/754241.html

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<string.h>
using namespace std;
char a[][];
int vis[][];
int ans = ;
void dfs(int i, int j)
{
if (i < || i> || j < || j>) //迷宫的出口
{
ans++;
return;
}
else
{
if (vis[i][j]) return; //如果已经搜过,直接返回 vis[i][j] = ; //标记已搜索 if (a[i][j] == 'L')
dfs(i, j - );
if (a[i][j] == 'R')
dfs(i, j + );
if (a[i][j] == 'U')
dfs(i - , j);
if (a[i][j] == 'D')
dfs(i + , j);
}
}
int main()
{
int i, j;
for (i = ; i < ; i++)
for (j = ; j < ; j++)
cin >> a[i][j]; for (i = ; i < ; i++)
for (j = ; j < ; j++)
{
memset(vis, , sizeof(vis)); //搜索每一个房间时,初始化搜搜数组
dfs(i, j);
}
cout << ans << endl;
return ;
}

暴力:文章地址https://www.yii666.com/article/754241.html网址:yii666.com

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<string.h>
using namespace std;
char a[][],c[][];
int vis[][];
int ans = ;
int main()
{ for (int i = ; i < ; i++)
{
for(int j=;j<;j++)
{
cin>>a[i][j];
c[i][j]=a[i][j];
}
} for (int i = ; i < ; i++)
{
for (int j = ; j < ; j++)
{
int x = i, y = j;
memset(vis, , sizeof(vis));
while ()
{ if (a[x][y] == 'U')
{
x = x - ;
if (x < || x> || y < || y>)
{
ans++;
c[i][j]='#';
break;
}
if (vis[x][y] == )
vis[x][y] = ;
else
break;
}
if (a[x][y] == 'L')
{
y = y - ;
if (x < || x> || y < || y>)
{
ans++;
c[i][j]='#';
break;
}
if (vis[x][y] == )
vis[x][y] = ;
else
break;
}
if (a[x][y] == 'R')
{
y = y + ;
if (x < || x> || y < || y>)
{
ans++;
c[i][j]='#';
break;
}
if (vis[x][y] == )
vis[x][y] = ;
else
break;
}
if (a[x][y] == 'D')
{
x = x + ;
if (x < || x> || y < || y>)
{
ans++;
c[i][j]='#';
break;
}
if (vis[x][y] == )
vis[x][y] = ;
else
break;
} }
}
}
cout << ans << endl;
// for(int i=0;i<10;i++)
// {
// for(int j=0;j<10;j++)
// cout<<c[i][j];
// cout<<endl;
// }
return ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png