| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2669 人关注过本帖
标题:请教:迷宫问题
取消只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏
已结贴  问题点数:100 回复次数:5 
请教:迷宫问题
题目描述
总算期中考了,鄙人被教育局分配到了SY学校,当然是陪着很多人的。不知转了多少次车,总算到了。可惜的是,SY学校整个像个迷宫一样,就在门口贴了张学校地图。鄙人就开始研究地图了,但是学校错综复杂,等找到目的地,早就开考了。为此,鄙人取出随身携带的微型电脑(不知道从哪来的),向网上发去了求助书。注:只能往4个方向走:上、下、左、右。

输入格式
第1行,二个数,N,M。
接下来是一个N*M的矩阵,表示这个学校。(有N行,M列)。矩阵由2个数字组成。0:路;1:墙。路能走,墙不能走(这是基本常识。不过还是提醒一下,不然哪个牛又要飞檐走壁了)。
再是2行,第1行2个数X1,Y1表示校门口的坐标(即校门口在矩阵的第X1行,第Y1列)。第2行2个数X2,Y2表示鄙人的考场的坐标(即校门口在矩阵的第X2行,第Y2列)。
数据范围:0<M,N<=2000。0〈X1,X2〈=N,0〈Y1,Y2〈=M。


输出格式
一个数,表示最少要走的步数。如果走不到,则输出 No Answer!

样例输入
5 5
1 1 1 1 1
1 1 1 0 0
1 0 0 0 1
0 0 1 0 0
1 1 1 0 1
4 1
5 4
样例输出
6

我的代码有点问题:
CODE:
#include <stdio.h>
#include <stdlib.h>
int maze[100][100];
static int step=0;
int endx,endy,m,n;
int flag;
int visit(int startx,int starty)
{
    //i=startx,j=starty  
    maze[startx][starty]=2;
    if(startx==endx&&starty==endy)
        flag=1;
    if(maze[startx][starty+1]
==0&&starty<n&&flag==0)//往右
    {
        if(maze[startx][starty+1]==2)
            step--;
        else
            step++;
        visit(startx,starty+1);
    }
    if(maze[startx+1][starty]
==0&&startx<m&&flag==0)//往下
    {
        if(maze[startx+1][starty]==2)
            step--;
        else
            step++;
        visit(startx+1,starty);
    }
    if(maze[startx][starty-1]
==0&&starty>1&&flag==0)//往左
    {
        if(maze[startx][starty-1]==2)
            step--;
        else
            step++;
        visit(startx,starty-1);
    }
    if(maze[startx-1][starty]
==0&&startx>1&&flag==0)//往上
    {
        if(maze[startx-1][starty]==2)
            step--;
        else
            step++;
        visit(startx-1,starty);
    }
    return step;     
}
void print_maze(int m,int n)
{
    int i,j;
    printf("print the maze map:\n");
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
    {
    if(j%5==0)
    printf("\n");
    printf("%d ",maze[i][j]);
    }
    system("pause");
}
int main()
{
    int i,j;
    int startx,starty;//起始坐标与结束坐

    scanf("%d %d",&m,&n);// 输入迷宫的行

    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
    scanf("%d",&maze[i][j]);//输入迷宫数

    //print_maze(m,n);//测试用,打印迷宫
    scanf("%d %d",&startx,&starty);
    scanf("%d %d",&endx,&endy);
    if(visit(startx,starty)==0)
    printf("No Answer!\n");
    else
        printf("step=%d",step);
    system("pause");
    return 0;
}
搜索更多相关主题的帖子: 迷宫 
2010-11-21 13:43
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
总算AC了,CODE:
#include <stdio.h>
#include <stdlib.h>
int maze[100][100];
static int step=0;
int endx,endy,m,n;
int flag;
int minstep = 100000;
void  visit(int startx,int starty)
{
 //i=startx,j=starty
 maze[startx][starty]=2;
 step++;
 if(startx==endx&&starty==endy) {
  flag=1;//actually useless
  if (step<minstep)
    minstep = step;
 }
 
 if(maze[startx][starty+1]==0&&starty<n)//往右
 {
  visit(startx,starty+1);
 }
 if(maze[startx+1][starty]==0&&startx<m)//往下
 {
  visit(startx+1,starty);
 }
 if(maze[startx][starty-1]==0&&starty>1)//往左
 {
  visit(startx,starty-1);
 }
 if(maze[startx-1][starty]==0&&startx>1)//往上
 {
  visit(startx-1,starty);
 }
 maze[startx][starty]=0;
 step--;
}
void print_maze(int m,int n)
{
 int i,j;
 printf("print the maze map:\n");
 for(i=0;i<m;i++)
  for(j=0;j<n;j++)
 {
 if(j%5==0)
 printf("\n");
 printf("%d ",maze[i][j]);
 }
 system("pause");
}
int main()
{
 int i,j;
 int startx,starty;//起始坐标与结束坐标
 scanf("%d %d",&m,&n);// 输入迷宫的行列
 for(i=1;i<=m;i++)
 for(j=1;j<=n;j++)
 scanf("%d",&maze[i][j]);//输入迷宫数据
 //print_maze(m,n);//测试用,打印迷宫
 scanf("%d %d",&startx,&starty);
 scanf("%d %d",&endx,&endy);
 visit(startx,starty);
 if (!flag)//could instead check 'if (minstep==100000)'
     printf("No Answer!\n");
 else
  printf("%d",minstep-1);//think why?
 return 0;
}

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-11-22 18:22
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 8楼 jack10141
好啊,网站 :www.

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-11-23 10:25
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 8楼 jack10141
欢迎到我的博客上来:http://blog.

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-11-23 10:26
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
回复 15楼 草狼
BFS已经AC了,递归还没有弄完

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-11-26 18:13
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
还有没有别的代码,给我参考一下?有好的代码给全分

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-11-26 18:19
快速回复:请教:迷宫问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.013092 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved