中易网

迷宫问题,C++解决,觉得没错然而错了,设断点发现第一个循环就有问题,求帮忙看一看啊!

答案:3  悬赏:60  
解决时间 2021-02-03 19:06
#include
#include
using namespace std;
char maze[101][101][101] = {0}; //存放输入的符号
int maze_mark[101][101] = {0}; //判断每个位置是否被走过,0表示没走过,1表示走过
int n; //规模大小
int one_x[101], one_y[101], two_x[101], two_y[101]; //(one_x, one_y)起始点,(two_x, two_y)终点
void my_function(int begin_x, int begin_y, int num)
{
if (begin_x < 0 || begin_x >= n)
return;
if (1 == maze_mark[begin_x][begin_y] || '#' == maze[begin_x][begin_y][num])
return;
else
{
maze_mark[begin_x][begin_y] = 1;
if ((begin_x - 1 >= 0) && (maze[begin_x - 1][begin_y][num] == '.') &&
(!maze_mark[begin_x - 1][begin_y]))
my_function(begin_x - 1, begin_y, num);
if ((begin_x + 1 < n) && (maze[begin_x + 1][begin_y][num] == '.') &&
(!maze_mark[begin_x + 1][begin_y]))
my_function(begin_x + 1, begin_y, num);
if ((begin_y - 1 >= 0) && (maze[begin_x][begin_y - 1][num] == '.') &&
(!maze_mark[begin_x][begin_y - 1]))
my_function(begin_x, begin_y - 1, num);
if ((begin_y + 1 < n) && (maze[begin_x][begin_y + 1][num] == '.') &&
(!maze_mark[begin_x][begin_y + 1]))
my_function(begin_x, begin_y + 1, num);
}
}
int main()
{
int cycle;
cin >> cycle;
while (cycle--)
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> maze[i][j][cycle];
cin >> one_x[cycle], one_y[cycle], two_x[cycle], two_y[cycle];
}
while (cycle--)
{
memset(maze_mark, 0, sizeof(maze_mark));
if ((one_x[cycle] == two_x[cycle]) && (one_y[cycle] == two_y[cycle])) //起始点就等于终点
{
cout << "YES" << endl;
continue;
}
if (two_x[cycle]< 0 || two_x[cycle] >= n || two_y[cycle] < 0 || two_y[cycle] >= n)
continue;
my_function(one_x[cycle], one_y[cycle], cycle);
if (maze_mark[two_x[cycle]][two_y[cycle]])
printf("YES\n");
else
printf("NO\n");
}
getchar();
return 0;
}

题目描述
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态, . 和#, 前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点 上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
输入格式
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为 . 或者 #。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出格式
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

样例输出
YES
NO
最佳答案
#include 
#include 
#include 

using namespace std;

const int maxn = 105;
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[maxn][maxn];
char maze[maxn][maxn];
int ha, la, hb, lb;
int n;

struct Node
{
    Node(int x, int y)
        :x(x), y(y){}
    int x, y;
};

bool bfs()
{
    queueq;
    q.emplace(ha, la);
    memset(vis, false, sizeof(vis));
    vis[ha][la] = true;
    while(!q.empty())
    {
        Node fr = q.front();
        q.pop();
        if(fr.x == hb && fr.y == lb)
        {
            return true;
        }
        for(int i = 0; i < 4; ++i)
        {
            int nx = fr.x + dir[i][0];
            int ny = fr.y + dir[i][1];
            if(0 <= nx && nx < n && 0 <= ny && ny < n && !vis[nx][ny] && maze[nx][ny] != '#')
            {
                q.emplace(nx, ny);
                vis[nx][ny] = true;
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                cin >> maze[i][j];
        cin >> ha >> la >> hb >> lb;
        if(bfs())
            cout << "YES" <         else
            cout << "NO" << endl;
    }
    return 0;
}
全部回答
能不能把题目和样例给一下?以方便解答
这个很像我们学习某计算机课的第一个项目0.0. 顺便问下你们学过stack或者queue么?deque学过也行?(再顺便问下你是上交的么?)
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
秸秆如何利用最好
和泰药堂地址在什么地方,想过去办事
北京的,要结婚,双方家长要见面,说订婚的事
BASIC 怎么拼读
光明路/南大街(路口)地址在哪,我要去那里办
天然气主管外自己安装的管道属于私有的吗
银川道/亚洲路(路口)在什么地方啊,我要过去
初遇变异妖兽怎么做
前穆楼这个地址在什么地方,我要处理点事
手表正准调整时间是逆转还是还是顺转?
插座插上去跳闸是线路问题还是插座
三星手机75681怎样取消通话时锁屏
之前我家的小狗把我家的八只小鸭子给咬死了,
七彩虹GT710黄金版1GD3是否还有人用?报价?
床头和卫生间一墙之隔如何化解
推荐资讯
16年高考三本大学是二个平行志愿吗
求歌名!其中歌词:……说我对你不够浪漫,我
速尔快递(化武路汇丰宾馆旁)地址在什么地方,
古代厕所是什么样的啊? 现代人穿过去会是什
汉朝,唐朝,明朝,清朝时期中日的往来和战争
日版iphone5打电话说没有开通这项业务怎么回
soundbose是什么牌子?
有只小僵尸出世,认了好多僵尸爸爸是什么电影
刮部产几年能要孩孑
韩国的多肉植物乒乓福娘老庄价钱是多少
看了僵尸世界大战会有心里病吗
暴走大事件脑残广告
手机登qq时,显示手机磁盘不足,清理后重新登
刺客的套装怎么选啊?