程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BFS PKU3984

BFS PKU3984

編輯:C++入門知識

BFS PKU3984


題目已經說了有唯一的解,所以只需要在找的過程中保存當前這個點前面的那個的點在隊列中的位置

然後再輸出的時候運用遞歸輸出就可以了。

迷宮問題 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8238 Accepted: 4848

Description

定義一個二維數組:
int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一個迷宮,其中的1表示牆壁,0表示可以走的路,只能橫著走或豎著走,不能斜著走,要求編程序找出從左上角到右下角的最短路線。

Input

一個5 × 5的二維數組,表示一個迷宮。數據保證有唯一解。

Output

左上角到右下角的最短路徑,格式如樣例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 10

int xx[4]={-1,0,1,0};
int yy[4]={0,1,0,-1};
int vis[MAXN][MAXN];
int map[MAXN][MAXN];
int ans;

struct node{
    int x,y;
    int pre;
}q[111];
int start=0;
int end = 1;

void print(int x){
    if(q[x].pre != -1){
        print(q[x].pre);
        printf("(%d, %d)\n",q[x].x,q[x].y);
    }
}

void BFS(int x,int y){
    int i;
    vis[x][y] = 1;
    q[start].x = x;
    q[start].y = y;
    q[start].pre = -1;
    while(start < end){
        if(q[start].x==4 && q[start].y==4){
            print(start);
        }
        for(i=0;i<4;i++){
            int dx = xx[i] + q[start].x;
            int dy = yy[i] + q[start].y;
            if(dx>=0 && dx<5 && dy>=0 && dy<5 && vis[dx][dy]==0 && map[dx][dy]==0){
                q[end].x = dx;
                q[end].y = dy;
                vis[dx][dy] = 1;
                q[end].pre = start;
                end++;
            }
            //if(dx==4 && dy==4){
            //    print(start);
            //}
        }
        start++;
    }
}

int main(){
    int i,j;
    for(i=0;i<5;i++){
        for(j=0;j<5;j++){
            cin>>map[i][j];
        }
    }
    memset(vis,0,sizeof(vis));
    printf("(0, 0)\n");
    BFS(0,0);
    //printf("(4, 4)\n");

    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved