백준 24725 엠비티아이 C++

Myers-Briggs Type Indicator (MBTI) is an introspective self-report questionnaire indicating differing psychological preferences in how people perceive the world and make decisions.

MBTI divides human personality into 16 types and each type consists of 4 alphabets.

• The first letter represents extroversion (E) or introversion (I), indicating how they gain their energy.
• The second letter represents intuition (N) or sensation (S), indicating how new information is understood and interpreted.
• The third letter represents emotions (F) or thinking (T), indicating how they make decisions.
• The last letter represents perception (P) or judgment (J), indicating lifestyle preferences how they organize their time.

There are 16 types of MBTI because a total of four alphabets are selected according to each description (e.g. ENFP, ISTP, ENTJ, etc.)

One day, you find an alphabet board while going to the laboratory. As you are too obsessed with MBTI, you start looking for how many MBTI types are on the board. If the four horizontal, vertical, or diagonal letters on the board are one of the types of MBTI, you will shout "MBTI!". The direction of the word does not matter, i.e. it could be the bottom right to top left, left to right, and so on. Also, even though the type is previously found, "MBTI!" should be shouted again if the word is in a different location or direction.

https://upload.acmicpc.net/21efb880-a4c9-428e-a069-513e79468fe5/-/preview/

https://upload.acmicpc.net/11bd8db4-cee4-4be2-8e9a-60cd8ccc966a/-/crop/873x780/3,0/-/preview/

https://upload.acmicpc.net/787300a6-36c6-488a-a13d-50d731e96196/-/crop/878x781/0,0/-/preview/

Figure 1.                            Figure 2.                             Figure 3.

Let's find all the MBTI types on the board and shout "MBTI!" together.

입력

Your program is to read from standard input. The input starts with an integer N,M$N, M$ ( 1≤N,M≤200$1 \leq N,M \leq 200$ ) representing rows and columns of boards. Following this are N$N$ lines containing M$M$ uppercase characters how does the alphabet board consist with.

출력

Your program is to write to standard output. Print exactly one line. The line should contain total occurrences of 16 MBTI types, which will be equal to the number of times you shouted 'MBTI!'

 

설명

DFS를 이용하여 (E,I)->(N,S)->(F,T)->(P,J) 순으로 존재하는지 전부 확인하면 MBTI 빙고를 외친다.

 

#include <iostream>
#include <queue>
#define MAX 200
using namespace std;
int n, m;
char board[MAX][MAX];
queue<pair<int, int>> q;

int dx[8] = { -1,-1, -1,0, 0, 1,1,1 };
int dy[8] = { -1, 0, 1, -1, 1, -1,0,1 };
char mbti[4][2] = { {'E', 'I'}, {'N', 'S'}, {'F', 'T'}, {'P', 'J'} };
int mbtiCount = 0;
void DFS(int idx, int x, int y, int dir) {
	if (idx == 3) {
		mbtiCount++;
		return;
	}
	else if (idx < 3) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
			return;
		}
		if (board[nx][ny] == mbti[idx + 1][0] || board[nx][ny] == mbti[idx + 1][1]) {
			//cout << idx + 1 << " " << board[nx][ny] << endl;
			DFS(idx + 1, nx, ny, dir);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

	for (int x = 0; x < n; x++) {
		for (int y = 0; y < m; y++) {
			if (board[x][y] == mbti[0][0] || board[x][y] == mbti[0][1]) {
				//cout << 0 << " " << board[x][y] << endl;
				for (int i = 0; i < 8; i++) {
					int nx = x + dx[i];
					int ny = y + dy[i];
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
						continue;
					}
					if (board[nx][ny] == mbti[1][0] || board[nx][ny] == mbti[1][1]) {
						//cout << 1 << " " << board[nx][ny] << endl;
						DFS(1, nx, ny, i);
					}
				}
			}
		}
	}

	cout << mbtiCount;
	return 0;
}