카드 짝 맞추기 C++

https://programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
struct Number { int x, y; };
vector<Number> v[7];
int sz = 0;
int answer = 987654321;
int R, C;
struct Move { int x, y; };
Move mv[4] = { { 0,-1 },{ -1,0 },{ 1,0 },{ 0,1 } };
vector<vector<int>> b;

int FindPath(int si, int sj, int  ei, int ej) {
	int visited[4][4];
	memset(visited, -1, sizeof(visited));
	queue<pair<pair<int, int>, int>> q;
	int count = 987654321;

	q.push(make_pair(make_pair(si, sj), 0));
	visited[si][sj] = 1;
	while (!q.empty()) {
		int ii = q.front().first.first;
		int jj = q.front().first.second;
		visited[ii][jj] = 1;
		int c = q.front().second;
		q.pop();

		if (ei == ii && ej == jj) {
			count = min(count, c);
			visited[ii][jj] = 0;
			continue;
		}

		for (int k = 0; k < 4; k++) {
			int movei = ii + mv[k].x;
			int movej = jj + mv[k].y;

			if (movei >= 0 && movei < 4 && movej >= 0 && movej < 4 && visited[movei][movej] == -1) {
				q.push(make_pair(make_pair(movei, movej), c + 1));

				bool flag = false;
				int i = movei;
				int j = movej;

				for (; i >= 0 && i < 4 && j >= 0 && j < 4; i += mv[k].x, j += mv[k].y) {
					if (visited[i][j] == -1 && b[i][j] != 0) {
						flag = true;
						q.push(make_pair(make_pair(i, j), c + 1));
					}
				}
				if (flag == false) {
					if (k == 0)	movej = 0;
					else if (k == 1)	movei = 0;
					else if (k == 2)	movei = 3;
					else if (k == 3)	movej = 3;
					if (visited[movei][movej] == -1) {
						q.push(make_pair(make_pair(movei, movej), c + 1));
					}
				}
			}
		}
	}
	return count;
}

void FindShortest(vector<pair<int, int>> seq) {
	int tmp = 0;
	int curi = R;
	int curj = C;
	int movei, movej;
	int board_copy[4][4];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			board_copy[i][j] = b[i][j];
		}
	}

	//b[curi][curj] = 0;
	for (int i = 0; i<seq.size(); i++) {
		movei = seq[i].first;
		movej = seq[i].second;
		int t = FindPath(curi, curj, movei, movej);
		b[movei][movej] = 0;
		tmp += (t + 1);
		curi = movei;
		curj = movej;
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			b[i][j] = board_copy[i][j];
		}
	}
	answer = min(answer, tmp);
}

void MakeTurn(vector<int> seq, vector<pair<int, int>> tmp, int turn) {

	if (turn == sz) {
		FindShortest(tmp);
	}
	else {
		tmp.push_back(make_pair(v[seq[turn]][0].x,v[seq[turn]][0].y));
		tmp.push_back(make_pair(v[seq[turn]][1].x, v[seq[turn]][1].y));
		MakeTurn(seq, tmp, turn + 1);
		tmp.pop_back();
		tmp.pop_back();
		tmp.push_back(make_pair(v[seq[turn]][1].x, v[seq[turn]][1].y));
		tmp.push_back(make_pair(v[seq[turn]][0].x, v[seq[turn]][0].y));
		MakeTurn(seq, tmp, turn + 1);
		tmp.pop_back();
		tmp.pop_back();
	}
}

void MakeSeq(int num, vector<int> seq) {
	if (num == sz) {
		vector<pair<int, int>> tmp;
		MakeTurn(seq, tmp, 0);
	}
	else {
		for (int i = 0; i<7; i++) {
			if (v[i].size() >0 && find(seq.begin(),seq.end(),i)==seq.end()) {
				seq.push_back(i);
				MakeSeq(num + 1, seq);
				seq.pop_back();
			}
		}
	}
}

int solution(vector<vector<int>> board, int r, int c) {
	R = r;
	C = c;
	b = board;
	for (int i = 0; i<board.size(); i++) {
		for (int j = 0; j<board[i].size(); j++) {
			if (board[i][j] != 0) {
				if (v[board[i][j]].size() == 0) {
					sz += 1;
				}
				v[board[i][j]].push_back({ i, j });
			}
		}
	}

	vector<int> tmp;
	MakeSeq(0, tmp);
	return answer;
}

int main(void) {
	cout << solution({ {1, 0, 0, 3},{2, 0, 0, 0},{0, 0, 0, 2},{3, 0, 1, 0} },1,0) << endl;
}