미궁 문제

4415 단어
컨베이어 도어
기점에서 종점까지 최단로의 경로를 인쇄하라고 합니다.구조체를 설정하여 선구와 현재 번호를 기록하고 그 종점의 번호를 찾아 출력 좌표로 귀속시키면 된다.
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int MAXN=30;
int dx[4]={0,0,1,-1};
int dy[4]={-1,1,0,0};
struct node{
    int x,y,pre,n;//pre n 
}point[MAXN];
int mp[5][5],vis[5][5];
int bfs(){
    memset(vis,0,sizeof(vis));
    int cnt=0;
    point[0]={0,0,-1,0};
    vis[0][0]=1;
    queueQ;
    Q.push(point[0]);
    node t;
    while(!Q.empty()){
        t=Q.front();
        Q.pop();
        int nowx=t.x,nowy=t.y,now=t.n;
        if(nowx==4&&nowy==4)return now;
        for(int i=0;i<4;i++){
            int gx=nowx+dx[i],gy=nowy+dy[i];
            if(gx<5&&gy<5&&gx>=0&&gy>=0&&mp[gx][gy]==0&&!vis[gx][gy])
            {vis[gx][gy]=1;
            point[++cnt]={gx,gy,now,cnt};
            Q.push(point[cnt]);
            }

        }
    }
}
void dfs(int x){
    if(point[x].n)dfs(point[x].pre);
    printf("(%d, %d)
",point[x].x,point[x].y);
}

int main(){
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            scanf("%d",&mp[i][j]);
    int ans=bfs();
    dfs(ans);
    return 0;
}
[FFC]no-repeats-please
컴파일링 원리

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage