企业收录网站有什么用域名查询网
标题:迷宫
X星球的一处迷宫游乐场建在某个小山坡上。
它是由10x10相互连通的小房间组成的。
房间的地板上写着一个很大的字母。
我们假设玩家是面朝上坡的方向站立,则:
L表示走到左边的房间,
R表示走到右边的房间,
U表示走到上坡方向的房间,
D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考。
他们更喜欢玩运气类的游戏。这个游戏也是如此!
开始的时候,直升机把100名玩家放入一个个小房间内。
玩家一定要按照地上的字母移动。
迷宫地图如下:
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
请你计算一下,最后,有多少玩家会走出迷宫?
而不是在里边兜圈子。
请提交该整数,表示走出迷宫的玩家数目,不要填写任何多余的内容。
如果你还没明白游戏规则,可以参看一个简化的4x4迷宫的解说图:
p1.png
PS:关于迷宫问题一般是搜索题,这道题可以用DFS也可以用BFS,详情如下
DFS
#include<stdio.h>
#include<math.h>
#include<string.h>
char mp[105][105];
int vis[105][105]={0};
int dfs(int x,int y){if(x<=0||y<=0||x>=11||y>=11) return 1;vis[x][y]=1;if(mp[x][y]=='L'){if(vis[x][y-1]==0)return dfs(x,y-1);else return 0;}if(mp[x][y]=='R'){if(vis[x][y+1]==0)return dfs(x,y+1);else return 0;}if(mp[x][y]=='U'){if(vis[x-1][y]==0)return dfs(x-1,y);else return 0;}if(mp[x][y]=='D'){if(vis[x+1][y]==0)return dfs(x+1,y);else return 0;}
}
int main()
{for(int i=1;i<=10;i++){scanf("%s",mp[i]+1);}int sum=0;for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){if(dfs(i,j)==1){printf("%d %d\n",i,j);sum++;}memset(vis,0,sizeof(vis));}}printf("%d\n",sum);
}
BFS
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{int x;int y;
};
int check(int xx,int yy)
{if(xx<=0||yy<=0||xx>=11||yy>=11)return 0;elsereturn 1;
}
char mp[15][15];
int vis[15][15];
int bfs(int a,int b)
{queue<node>q;while(q.size())q.pop();node now;now.x=a;now.y=b;vis[a][b]=1;q.push(now);while(q.size()){node m;node k=q.front();q.pop();if(check(k.x,k.y)==0){return 1;}else{//printf("%d + %d %c\n",k.x,k.y,mp[k.x][k.y]);if(mp[k.x][k.y]=='R'&&vis[k.x][k.y+1]==0){m.y=k.y+1;m.x=k.x;vis[m.x][m.y]=1;q.push(m);}else if(mp[k.x][k.y]=='L'&&vis[k.x][k.y-1]==0){m.y=k.y-1;m.x=k.x;vis[m.x][m.y]=1;q.push(m);}else if(mp[k.x][k.y]=='U'&&vis[k.x-1][k.y]==0){//printf("++++\n");m.x=k.x-1;m.y=k.y;vis[m.x][m.y]=1;q.push(m);}else if(mp[k.x][k.y]=='D'&&vis[k.x+1][k.y]==0){m.x=k.x+1;m.y=k.y;vis[m.x][m.y]=1;q.push(m);}//printf("%d - %d\n",m.x,m.y);}}return 0;
}
int main()
{for(int i=1; i<=10; i++){scanf("%s",mp[i]+1);}int sum=0;// bfs(1,2);for(int i=1; i<=10; i++){for(int j=1; j<=10; j++){if(bfs(i,j)==1){printf("%d %d\n",i,j);sum++;}memset(vis,0,sizeof(vis));}}printf("%d\n",sum);
}