BFS(普通队列与循环队列实现)---OJ 1241 油田问题

淡淡的烟草味﹌ 2023-10-17 14:33 32阅读 0赞

## Oil Deposits ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 32184 Accepted Submission(s): 18680**

Problem Description

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either \`\*', representing the absence of oil, or \`@', representing an oil pocket.

Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.

Sample Input

1 1 \* 3 5 \*@\*@\* \*\*@\*\* \*@\*@\* 1 8 @@\*\*\*\*@\* 5 5 \*\*\*\*@ \*@@\*@ \*@\*\*@ @@@\*@ @@\*\*@ 0 0

Sample Output

0 1 2 2

普通队列应用:

public class PlotQueue {
    	Plot plots[] = new Plot[100];
    	final int FRONT = 0; // 代表指针
    	int end = 0;
    
    	public void add(Plot p) {
    		plots[end] = p;
    		end++;    
    	}
    
    	public boolean isEmpty() {
    		return end == 0;    //队列为空时,则返回false
    	}
    
    	public Plot pop() {
    		if (isEmpty()) {
    			return null;
    		}
    
    		Plot p = plots[FRONT];
    		if (end > 1) {
    			for (int i = 0; i < end; i++) { // //如果多于1个元素，需把后续中的每个元素往前移一位
    				plots[i] = plots[i + 1];
    			}
    		}
    		end--;
    		return p;
    
    	}
    }

下面是循环队列的应用: 一般循环队列都会多开一个空间,以便于循环储存

public class CirclingQueue {
    	private Plot plots[];
    	private int front;
    	private int end;
    	private final int MAX_SIZE = 80; // 0~79
    
    	public CirclingQueue() {
    		plots = new Plot[MAX_SIZE];
    		front = 0;
    		end = 0;
    	}
    
    	public void add(Plot p) {
    		if (isFull()) {
    			System.out.println("队列已满,添加失败!");
    			return;
    		}
    		plots[end] = p;
    		end = (end + 1) % MAX_SIZE; //这里是与普通队列的重点区别之一
    	}
    
    	private boolean isFull() {
    		return (end + 1) % MAX_SIZE == front;
    	}
    
    	public boolean isEmpty() {
    		return front == end;
    	}
    
    	public Plot pop() {
    		if (isEmpty()) {
    			System.out.println("队列以空,弹出失败!");
    			return null;
    		}
    
    		Plot p = plots[front];
    		front = (front + 1) % MAX_SIZE;
    		return p;
    
    	}
    
    }

下面就是公共部分的代码实现:

public class Plot {
        int x,y; //位置x行y列
        char c;  //代表字符
        boolean isVisited = false;// 代表节点是否被访问
        
    }

//题意:输入一片区域,找出油田的片数,这里是指'@'代表一个油点,它分别与八个方向相邻的'@'构成一片油田,如果只有它一个点也称为一片油田
    
    import java.util.Scanner;
    
    public class Main {
    	final static int dir[][] = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
    			{ -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 }
    
    	};
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		while (sc.hasNext()) {
    			int m = sc.nextInt();
    			int n = sc.nextInt();
    			if (m == 0) {
    				return;
    			}
    			// 创建图
    			Plot plots[][] = new Plot[m][n];
    			// 初始化图
    			for (int i = 0; i < m; i++) {
    				String str = sc.next();
    				for (int j = 0; j < n; j++) {
    					plots[i][j] = new Plot(); // 重新new一个对象(每一次都new对象 )
    					plots[i][j].c = str.charAt(j); // 在位置上输入一个字符
    					plots[i][j].x = i; //
    					plots[i][j].y = j;
    				}
    			}
    			// 搜森林
    			int count = 0;
    			for (int i = 0; i < m; i++) {
    				for (int j = 0; j < n; j++) {
    					if (plots[i][j].c == '@' && !plots[i][j].isVisited) {
    						// 从plots[i][j]发起一次广搜，搜出一片油田并且把搜过节点涂色(作标记)
    						PlotQueue queue = new PlotQueue();  //普通队列使用
    						// CirclingQueue queue = new  CirclingQueue();//########循环队列使用
    						
    						plots[i][j].isVisited = true; // 入队列前标记已经搜
    						queue.add(plots[i][j]);
    
    						boolean isGon = false;
    						while (!queue.isEmpty()) {
    							isGon = true;
    							Plot plot = queue.pop();
    							for (int k = 0; k < 8; k++) { // 遍历当前图块的所有邻居节点
    								int px = plot.x + dir[k][0];
    								int py = plot.y + dir[k][1];
    
    								// v==plots[px][py]
    								if (px >= 0 && px < m && py >= 0 && py < n
    										&& // 这一行必须写在前面，利用短路来防护下一行
    										plots[px][py].c == '@'
    										&& !plots[px][py].isVisited) {
    									plots[px][py].isVisited = true;
    									queue.add(plots[px][py]);
    								}
    
    							}
    
    						}
    						// 统计搜索的次数
    						if (isGon) {
    							count++;
    						}
    
    					}
    				}
    
    			}
    			System.out.println(count);
    		}
    	}
    }