백준 2210번 숫자판 점프 C++

출처 : https://www.acmicpc.net/problem/2210

 

1. 백트래킹으로 5번 이동하는 경우를 모두 구한다.

2. 모든 칸에 대하여 1에서 구한 이동하는 경우를 적용한다.

3. 2의 과정에서 6자리수를 만들 수 있으면 그 수를 set에 넣는다.

4. set의 size를 출력한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

vector<vector<int>> board(5, vector<int>(5));
vector<int> dirV;
set<int> s;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

void Solve() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			int row = i;
			int col = j;
			int sum = board[i][j];
			bool isPossible = true;
			for (int k = 0; k < dirV.size(); k++) {
				int nextRow = row + dRow[dirV[k]];
				int nextCol = col + dCol[dirV[k]];
				if (nextRow < 0 || nextRow >= 5) {
					isPossible = false;
					break;
				}
				if (nextCol < 0 || nextCol >= 5) {
					isPossible = false;
					break;
				}
				row = nextRow;
				col = nextCol;
				sum = sum * 10 + board[nextRow][nextCol];
			}
			if (isPossible) {
				s.insert(sum);
			}
		}
	}
}

void BT(int cnt) {
	if (cnt >= 5) {
		Solve();
		return;
	}
	for (int i = 0; i < 4; i++) {
		dirV.push_back(i);
		BT(cnt + 1);
		dirV.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> board[i][j];
		}
	}
	BT(0);
	cout << s.size();
};