import java.util.ArrayList;
import java.util.HashMap;

class Solution {
 	ArrayList<Block> list = new ArrayList<Block>();
	public int solution(int m, int n, String[] board) {
		int answer = 0;
		int id = 0;
		int eachRow = 0;
		for (int i = 0; i < m; i++) {
			String[] eachLetter = board[eachRow].split("");
			int getLetter = 0;
			for (int j = 0; j < n; j++) {
				Block block = new Block(id, eachLetter[getLetter], i, j);
				list.add(block);
				id++;
				getLetter++;
			}
			eachRow++;
		}

		while (true) {
			/* 4 blocks를 탐색한다 */
			HashMap<Integer, Boolean> fourMap = fourBlockSearch(m, n, board);
			if (fourMap.get(-1) == false) {
				break;
			}
			/* fourMap대로 letter 변경 */
			id = 0;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					if (fourMap.get(id) == true) {
						list.get(id).letter = "x";
					}
					id++;
				}
			}

			/* x로 입력되어있는 아래 줄 라인의 id를 lowerLineSearch에 담는다 */
			HashMap<Integer, Integer> lowerLineMap = new HashMap<Integer, Integer>();
			lowerLineMap = lowerLineSearch(m, n, board);

			/* 각 Column마다 새로운 값을 넣어 줄 switchTarget list를 만든다 */
			ArrayList<ArrayList<String>> switchTarget = new ArrayList<ArrayList<String>>();
			for (int i = 0; i < n; i++) {
				switchTarget.add(insertUpperLetters(i, lowerLineMap, m, n, board));
			}

			/*
			 * lowerLineMap을 탐색하면서, switchTarget의 값을 맨 아래줄 x부터 각 switchTarget의 list size만큼
			 * 담아준다
			 */
			switchLetter(lowerLineMap, switchTarget, m, n);
		}
		/* 전체 블록의 x의 개수를 헤아려준다 */
		for (int i = 0; i < list.size(); i++) {
			if (list.get(i).letter.equals("x")) {
				answer++;
			}
		}
		return answer;

	}

	public void switchLetter(HashMap<Integer, Integer> lowerLineMap, ArrayList<ArrayList<String>> switchTarget, int m,
			int n) {
		for (int i = 0; i < n; i++) {
			int start = lowerLineMap.get(i);
			if (start < 0) {
				continue;
			}
			for (int j = 0; j < switchTarget.get(i).size(); j++) {
				list.get(start).letter = switchTarget.get(i).get(j);
				start -= n;
			}
		}
	}

	/* 2x2 block을 탐색하는 메소드 */
	public HashMap<Integer, Boolean> fourBlockSearch(int m, int n, String[] board) {
		HashMap<Integer, Boolean> fourMap = new HashMap<Integer, Boolean>();
		/* 2x2블록이 아무것도 없으면 key = -1 일 때 값은 false다. */
		fourMap.put(-1, false);
		for (int i = 0; i < list.size(); i++) {
			fourMap.put(i, false);
		}
		for (int i = 0; i < list.size(); i++) {
			Block block = list.get(i);
			int count = 0;
			/* 오른쪽 탐색 */
			if (block.y < n - 1) {
				/* blcok의 letter 값이 x일때는 탐색하지 않는다 */
				if (list.get(i + 1).letter.equals("x")) {
					continue;
				}
				if (list.get(i + 1).letter.equals(block.letter)) {
					count++;
				}
			}
			/* 아래쪽 탐색 */
			if (block.x < m - 1) {
				if (list.get(i + n).letter.equals(block.letter)) {
					count++;
				}
			}
			/* 대각선 탐색 */
			if (block.y < n - 1 && block.x < m - 1) {
				if (list.get(i + n + 1).letter.equals(block.letter)) {
					count++;
				}
			}
			if (count == 3) {
				fourMap.replace(i, true);
				fourMap.replace(i + 1, true);
				fourMap.replace(i + n, true);
				fourMap.replace(i + n + 1, true);
				fourMap.replace(-1, true);
			}
		}
		return fourMap;
	}

	/* 각 컬럼의 가장 아래쪽 x의 block id를 찾아서 HashMap으로 반환 */
	public HashMap<Integer, Integer> lowerLineSearch(int m, int n, String[] board) {
		HashMap<Integer, Integer> lowerLineMap = new HashMap<Integer, Integer>();
		for (int i = 0; i < n; i++) {
			for (int j = m * n - n + i; j >= 0; j -= n) {
				Block block = list.get(j);
				if (block.letter.equals("x")) {
					lowerLineMap.put(i, block.id);
					break;
				}
				lowerLineMap.put(i, -1);
			}
		}
		return lowerLineMap;
	}

	/* 각 컬럼을 세로로 가장 아래쪽 x부터 탐색하면서, 문자를 list에 저장함과 동시에 x로 변환해줌 */
	public ArrayList<String> insertUpperLetters(int column, HashMap<Integer, Integer> lowerLineMap, int m, int n,
			String[] board) {
		ArrayList<String> listOfNotX = new ArrayList<String>();

		for (int i = lowerLineMap.get(column); i >= 0; i -= n) {
			if (!list.get(i).letter.equals("x")) {
				listOfNotX.add(list.get(i).letter);
				list.get(i).letter = "x";
			}
		}
		return listOfNotX;
	}

}

class Block {
	int id;
	String letter;
	int x;
	int y;

	public Block(int id, String letter, int x, int y) {
		this.id = id;
		this.letter = letter;
		this.x = x;
		this.y = y;
	}
}