/**

BFS 解题思路

特点：从某些特定的节点开始，感染相邻的节点; 被感染的节点，再感染其相邻的节点，以此类推。

题目常见于数据结构包括 二维数组、树、图

**/

/**

1). 二维数组特定节点感染相邻的节点，即上下左右四个方向，可设定变化数组如下

int[] dr = new int[]{-1, 0, 1, 0};

int[] dc = new int[]{0, -1, 0, 1};

2). 二维数组特定节点感染包围它的节点，即八个方法, 可设定变化数组如下：

int[] dr = new int[]{-1, -1, -1, 0, 0, 1, 1, 1};

int[] dc = new int[]{-1, 0, 1, -1, 1, -1, 0, 1};

**/

//BFS的目的是通过遍历特定节点及可能被感染的节点，以计算出要求的结果。可能求最大最小值，也可能是统计数量等等。

//这里定义一个内部类来存储每个节点的坐标及计算结果。

class Node{

	int r;

	int c;

	int val;

	public Node(int r, int c, int val){

		this.r = r;

		this.c = c;

		this.val = val;

	}

}

//定义一个队列(FIFO, 先进先出)来存储所有涉及的节点

Queue<Node> queue = new LinkedList<Node>();

//遍历二维数组 grid

int R = grid.length, C = grid[0].length;

for(int r = 0; r < R; r++){

	for(int c = 0; c < C; c++){

		//isNeedToAdd 按实际实现，一般由索引值和实际值两种因素决定

		if(isNeedToAdd(r, c, grid[r][c])){

			int val = ...;//计算出结果

			queue.add(new Node(r, c, val));

		}

	}

}

//BFS

//注意：BFS 不一定就直接得出最终的答案，可能得到的是最终答案的前置变量, 这里需要分析一下从 BFS 得到的结果如何可以转换到最终答案。

//定义最终结果变量 ans

int ans = 0;

while(!queue.isEmpty()){

	Node node = queue.poll();

	for(int k = 0; k < 4; k++){

		int nr = node.r + dr[k];

		int nc = node.c + dr[k];

		//首先需要判断边界

		if(nr >= 0 && nr < R && nc >= 0 && nc < C){

			//备忘录判断：为了不重复处理已搜查过的节点

			//备忘录处理方法有几种：1. 改变已搜查过的节点的值，通过值进行判断, 这种方法不占用额外存储空间; 2. 使用哈希表

			if(!memoExist(nr, nc, grid[nr][nc])){//备忘录不存在则继续

				addToMemo();//加入备忘录

				int nval = ....;//计算出结果

				ans = ....;//使用中间结果计算出最后结果，例如求最大值 ans = Math.max(ans, nval);

				queue.add(new Node(nr, nc, nval))

			}

		}

	}

}