사천성 - 4방향 진행, 여기서 한 번 더 꺾는거 고려

#include<iostream>
#include <vector>

using namespace std;

int dx[] = { 0, 1, 0, -1 };
int dy[] = {1, 0, -1, 0};
int var;

struct pos {
	int x, y;
};

//각 알파벳 쌍의 x, y 좌표를 저장할 벡터
vector<vector<pos>> xypos(26);
vector<string> board;

bool reachable(vector<string> board, char c, pos from, pos to, int m, int n) {
	//4방향 진행시켜보기
	for (int i = 0; i < 4; i++) {
		int nx = from.x + dx[i];
		int ny = from.y + dy[i];

		while (!(nx < 0 || nx >= m || ny < 0 || ny >= n)) 
			//.가 아니라면, 진행 불가. 브레이크
			//4방향 내에 to가 있다면 true 반환
			if (nx == to.x && ny == to.y) {
				return true;
			}
			if (board[nx][ny] != '.') {
				break;
			}

			//위아래로 이동했으면 한 번은 양옆, 양옆으로 이동했으면 한번은 위아래로 가본다
			//i==0, 2일땐 위아래로, 1,3일땐 양옆으로 간것
			for (int j = (i + 1) % 2; j < 4; j += 2) {
				int nnx = nx + dx[j]; 
				int nny = ny + dy[j];

				while (!(nnx < 0 || nnx >= m || nny < 0 || nny >= n)) {
					//위와 같은 조건.
					if (nnx == to.x && nny == to.y) {
						return true;
					}
					if (board[nnx][nny] != '.') {
						break;
					}

					//전에 진행한 방향으로 다시 한 번 진행
					nnx += dx[j];
					nny += dy[j];
				}
			}

			//전에 행한 방향으로 다시 한번 진행
			nx += dx[i];
			ny += dy[i];
		}
	}
	return true;
}

string solve(int m, int n, vector<string> m_board) {

	board = m_board;

	//일단 board 처리 시작
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (isalpha(board[i][j])) {
				var++; //총 알파벳 개수
				//각 알파벳에 해당한 벡터로, {i, j} 구조체를 삽입
				xypos[board[i][j] - 'A'].push_back({ i, j });
			}
		}
	}

	string answer = "";
	while (true) {
		bool match = false; //짝 맞춰보자

		//알파벳 순으로, 가장 먼저인 문자열의 출력이 필요
		for (int i = 0; i < 26; i++) {
			//맞춰야 할 짝이 남아 있다면
			if (!xypos[i].empty()) {
				char ch = i + 'A';
				pos from = xypos[i][0];
				pos to = xypos[i][1];

				//만약 두 알파벳이 1번 이하로 꺾어서 만날 수 있다면
				if (reachable(board, ch, from, to, m, n)) {
					answer += ch;

					//알파벳이 있던 장소를 없앴으니 빈칸처리 한다
					board[from.x][from.y] = '.';
					board[to.x][to.y] = '.';
					//다음으로, 그 알파벳 벡터를 clear
					xypos[i].clear();

					match = true;
					var -= 2;
					break;
				}
			}
		}

		if (!match) {
			break;
		}
	}

	if (var == 0) return answer;
	return "IMPOSSIBLE";
}

int main() {
	vector<string> board = { "DBA", "C*A", "CDB" };
	string ans = solve(3, 3, board);
	cout << ans << "\n";
	return 0;
}