您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

蓝桥杯2017A组c++迷宫问题

题目描述

X星球的一处迷宫游乐场建在某个小山坡上。 它是由10x10相互连通的小房间组成的。房间的地板上写着一个很大的字母。 我们假设玩家是面朝上坡的方向站立,则: L表示走到左边的房间, R表示走到右边的房间,U表示走到上坡方向的房间, D表示走到下坡方向的房间。
X星球的居民有点懒,不愿意费力思考在这里插入代码片。 他们更喜欢玩运气类的游戏。这个游戏也是如此!开始的时候,直升机把100名玩家放入一个个小房间内。 玩家一定要按照地上的字母移动。

迷宫如下

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

解题思路
DFS加二维标记数组,标记走过的地方,ans+1即可
代码如下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
string data[10];
int ans;
int vis[10][10];
bool solve(int i, int j){       //DFS
    if(i < 0 || i > 9 || j < 0 || j > 9)
        return true;        //出迷宫
    if(vis[i][j] == 1)  return false;
    vis[i][j] = 1;  //访问过则将vis[i][j]设为1
    switch(data[i][j]){
        case 'U':
            return solve(i - 1, j);  //如果向上走,坐标 i 减 1 
        case 'D':
            return solve(i + 1, j);
        case 'L':
            return solve(i, j - 1);
        case 'R':
            return solve(i, j + 1);
        default:
            return false;
    }
}
int main(){
    /*data[10]={"UDDLUULRUL","UURLLLRRRU","RRUURLDLRD","RUDDDDUUUU","URUDLLRRUU","DURLRLDLRL","ULLURLLRDU",
    "RDLULLRDDD","UUDDUDUDLL","ULRDLUURRR"};   //迷宫地图   */
    data[0] = "UDDLUULRUL";
    data[1] = "UURLLLRRRU";
    data[2] = "RRUURLDLRD";
    data[3] = "RUDDDDUUUU";
    data[4] = "URUDLLRRUU";
    data[5] = "DURLRLDLRL";
    data[6] = "ULLURLLRDU";
    data[7] = "RDLULLRDDD";
    data[8] = "UUDDUDUDLL";
    data[9] = "ULRDLUURRR";
    for (int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            memset(vis, 0 ,sizeof(vis)); //对于每一个点均需要初始化为0
            bool res = solve(i , j);
            if(res)
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进