首页 > 其他 > 详细

油田问题 bfs

时间:2020-07-19 22:38:57      阅读:71      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

技术分享图片

 

 技术分享图片

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <queue>
using namespace std;
int N=0;
int ax[8]={0,0,1,-1,1,1,-1,-1};
int ay[8]={1,-1,0,0,-1,1,-1,1};
//bfs队列加对象,对象就是队列的类型,在这个题中就可以直接用x,y
//满足条件(为#)的对象插入队列
struct Point{
    int x;
    int y;
};
queue<Point> q;
//标记是否到达
int mark[103][103]={0};
char data[103][103];
void bfs(int i,int j,int a,int b){
    mark[i][j]=1;
    q.push({i,j});
    N++;
    while(!q.empty()){
        Point first=q.front();
        q.pop();
        for (int k = 0; k < 8; ++k) {
            int x=first.x+ax[k];
            int y=first.y+ay[k];
            if(x>=0 && x<a && y>=0 && y<b && data[x][y]==@ && mark[x][y]==0){
                mark[x][y]=1;
                q.push({x,y});
            }

        }
    }
}
int main(){
    int a,b;
    while(cin>>a>>b) {
        if(a==0 && b==0){
            break;
        }
        N=0;
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < b; ++j) {
                cin >> data[i][j];

            }

        }


        for (int k = 0; k < a; ++k) {
            for (int l = 0; l < b; ++l) {
                //cout<<data[k][l]<<endl;
                if (data[k][l] == @ && mark[k][l]==0) {

                    bfs(k, l, a, b);
                }

            }

        }
        cout << N<<endl;
        for (int i = 0; i < a; ++i) {
            for (int j = 0; j < b; ++j) {
               data[i][j]=0;

            }

        }

        for (int m = 0; m < 103; ++m) {
            for (int i = 0; i < 103; ++i) {
                data[m][i]=0;
                mark[m][i]=0;

            }

        }

    }


}

 

油田问题 bfs

原文:https://www.cnblogs.com/zhmlzhml/p/13340892.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!