电子老鼠闯迷宫noj

10/27 10:39
阅读数 51

在这里插入图片描述
在这里插入图片描述

#include<iostream>
#include<queue>
using namespace std;
#define true 1
#define false 0
#define MAXN 1000

char maze[12][12];//游戏背景图
int used[MAXN][MAXN];//记录某点是否走过
int step[MAXN][MAXN];//记录走过的步数
struct node{
   
   
    int x;
    int y;
};
node start;
queue<node>q1;
int sx,sy,ex,ey;//记录起点,终点
int walk[4][2]={
   
   
    0,1,
    0,-1,
    1,0,
    -1,0
};
int dfs();
int isTarget(node now,node next);
int main()
{
   
   
    int i,j;
    cin>>sx>>sy>>ex>>ey;
    sx--;
    sy--;
    ex--;
    ey--;
    start.x=sx;
    start.y=sy;
    q1.push(start);
    used[start.x][start.y]=1;
    for(i=0;i<12;i++){
   
   
        for(j=0;j<12;j++){
   
   
            cin>>maze[i][j];
        }
    }
    cout<<dfs()<<endl;
    return 0;
}
int dfs()
{
   
   
    node now,next;
    int i;
    while(!q1.empty()){
   
   
        now=q1.front();
        q1.pop();
        for(i=0;i<4;i++){
   
   
            next.x=now.x+walk[i][0];
            next.y=now.y+walk[i][1];
            if(isTarget(now,next)){
   
   
                return step[next.x][next.y];
            }
        }
    }
}
int isTarget(node now,node next)
{
   
   
    if(next.x>=0&&next.x<12&&next.y>=0&&next.y<12){
   
   
        if(!used[next.x][next.y]){
   
   
            if(maze[next.x][next.y]!='X'){
   
   
                used[next.x][next.y]=1;
                step[next.x][next.y]=step[now.x][now.y]+1;
                if(next.x==ex&&next.y==ey){
   
   
                    return true;
                }
                else q1.push(next);
            }
        }
    }
    return false;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部