hur.cn - 华软网

 热门搜索

一个另类的迷宫问题,墙不是方格

  作者:未知    来源:网络    更新时间:2011/10/4
一个迷宫是由R*C的网格表示。迷宫只有一个出口和入口。 迷宫的入口在第一行,出口在最底行。
输入第一行四个正数R,C,ENT,EXIT(2<=R<=200,2<=C<=200),表示R行,C列,入口在ENT列,出口在EXIT列。接下2*R-1行,第2*i行有C-1个数,第J个数表示网格g[i][j]与g[i][j+1]之间有墙壁。第2*i+1行有C个数,第J个数表示网格g[i][j]和g[i+1][j]之间有墙壁。0表示没有墙壁,1表示两个位置之间有墙壁。
如有有路径走出,则输出最短的步数,否则输出“No Way ”(引号去掉)。

示意图:
http://ds.fzu.edu.cn/Uploads/Problem/SimpleMaze.pdf


这个和常见的迷宫问题又不一样,求解啊

另外:怎样将输入的墙的数值,转换为方格那样的形式。
比如输入
1
0 0
0

转换成布线问题的就是下面的矩阵
1 0
0 0 0
0 0
---华软 网友回答---
这个题看着有点复杂
那个输入木有看懂
---华软网友回复---
引用 1 楼 udbwcso 的回复:
这个题看着有点复杂
那个输入木有看懂

输入的0和1就是墙的虚实,这里墙是竖线和横线,不是方格,所以我感觉需要转换,就是不知怎么转换。
---华软网友回复---
直接BFS...
---华软网友回复---
对照你给的链接就很清晰了啊

---华软网友回复---
我是这样写的,但是墙的问题依然按照典型的方式输入的,所以请教怎么修改才能达到题目输入的要求?
C++">#include<iostream>
#include<cstdlib>
#include<queue>
#define MAXSIZE 100


using namespace std;  

typedef struct point  
{  
    int x;  
    int y;  
}point;  
point start,end;                    //起点,终点  
int n,m;                              //大小  
int graph[MAXSIZE][MAXSIZE];        //二维矩阵  
int total=0;                        //总步数  

void input();                       //输入  
bool find();                        //计算  
void output();                      //输出  

int main(void)  
{  
    input();  
    find();  
    output();  
    return 0;  
}  

void input()  
{  
    cin>>n;  cin>>m;
    cin>>start.x;  
    cin>>end.x;  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=m;j++)  
        {  
            cin>>graph[i][j];                                             //1表示墙,0表示空  
        }  
    }  
}  

bool find()  
{  
    if(start.x==end.x&&1==m)  
    {  
        total=0;  
        return true;  
    }  
    queue<point> q;  
    graph[start.x][1]=2;  
    point top;  
    top.x=start.x;  
    top.y=1;  
    point temp;  
    temp.x=0;  
    temp.y=0;  
    int numberOfDirection=4;  
    point direction[4];  
    direction[0].y=1;  
    direction[0].x=0;  
    direction[1].y=0;  
    direction[1].x=1;  
    direction[2].y=-1;  
    direction[2].x=0;  
    direction[3].y=0;  
    direction[3].x=-1;  
    do  
    {  
        for(int i=0;i<numberOfDirection;i++)  
        {  
            temp.x=top.x+direction[i].x;  
            temp.y=top.y+direction[i].y;  
            if(graph[temp.x][temp.y]==0 && temp.x>=1&&temp.x<=n && temp.y>=1&&temp.y<=n)  
            {  
                graph[temp.x][temp.y]=graph[top.x][top.y]+1;  
                if(temp.x==end.x&&temp.y==m)  
                {  
                    break;  
                }  
                q.push(temp);  
            }  

        }  
        if(temp.x==end.x&&temp.y==m)  
        {  
            break;  
        }  
        if(q.empty())  
        {  
            return false;  
        }  
        top=q.front();  
        q.pop();  
    }while(1);  
    total=graph[end.x][m]-2;  
    return true;  
}  

void output()  
{  
    cout<<total<<endl;  
}  

---华软网友回复---
你是没理解墙的信息的含义吧?
以你给的材料为例
4*3的迷宫有横纵相间的线围成的
每一行有四条横线
间隔下来就是五条竖线
由于边框不需要考虑所以就是3条竖线
这样从第二号开始的数字的意义你对应图一看也就明白了
---华软网友回复---
引用 6 楼 xianglitian 的回复:
你是没理解墙的信息的含义吧?
以你给的材料为例
4*3的迷宫有横纵相间的线围成的
每一行有四条横线
间隔下来就是五条竖线
由于边框不需要考虑所以就是3条竖线
这样从第二号开始的数字的意义你对应图一看也就明白了


意思理解了,只是不会实现,我的疑问就是想把输入的墙转化成方格类型的矩阵
---华软网友回复---
我觉得这个问题不应该用放个类型的矩阵
或者说应该辅助一个墙的矩阵      
华软声明:本内容来自网络,如有侵犯您版权请来信指出,本站立即删除。