首页 > 代码库 > 僵尸传染问题demo(BFS)

僵尸传染问题demo(BFS)

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
typedef struct node{
    int x;
    int y;
    int step;
}node;
int map[SIZE][SIZE]={{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1}};
node queue[30];
int head,tail;//队列头和队列尾
int step;
int x[4]={-1,0,+1,0};//x坐标的变化
int y[4]={0,+1,0,-1};//y坐标的变化
/* 函数名:enqueue
*  功能:入队
*  入口参数:要入队的节点
*  返回值:暂无
*/
void enqueue(node E){//用tail(对尾)进行插入操作
    queue[tail++] = E;//先入队,然后tail加一
}
/* 函数名:dequeue
*  功能:出队
*  入口参数:要出队的节点
*  返回值:出队的元素
*/
node dequeue(){//用head(队头)进行删除操作
    return queue[head++];//先出队,然后head加一
}

int main(){
    //源点入队列
    node SourcePoint ={4,4,2};
    enqueue(SourcePoint);
    step = 0;
    int count=3;
    map[4][4] = 2;//把传染源置为2
    node CurPoint ={};//当前点
    node NewPoint ={};//新的点
    while(head<tail){
        
        CurPoint = dequeue();//当前点出队列
        for(int i=0;i<4;i++){
            NewPoint.x = CurPoint.x + x[i];
            NewPoint.y = CurPoint.y + y[i];
            NewPoint.step = CurPoint.step+1;

            if((NewPoint.x<SIZE&&NewPoint.y<SIZE)&&(map[NewPoint.x][NewPoint.y]==1))
            {
                //CurPoint.x = NewPoint.x;
                //CurPoint.y = NewPoint.y;
                //map[CurPoint.x][CurPoint.y]=count;
    //             enqueue(CurPoint);

                  map[NewPoint.x][NewPoint.y] = NewPoint.step;
                  enqueue(NewPoint);

            }
        }
    }
    for(int i=0;i<SIZE;i++){
        for(int j=0;j<SIZE;j++)
        {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
 //     { printf("%d",map[i]);
    //printf("\n");}
    system("pause");
}

 

僵尸传染问题demo(BFS)