[DFS 중복순열] 백준 17070 파이프 옮기기1 C++

 

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

방향 중복하여 선택 가능

#include <bits/stdc++.h>

using namespace std;

int n, ans, board[18][18];
int dx[4] = { 0, 1, 1 };
int dy[4] = { 1, 0, 1 };

void dfs(int x, int y, int dir) {
	if ((x == n) && (y == n)) {
		ans++;
		return;
	}

	for (int i = 0; i < 3; i++) {
		int newX = x + dx[i];
		int newY = y + dy[i];

		if ((newX == 0) || (newY == 0) || (newX > n) || (newY > n)) continue;

		if (i == 0) {
			if (dir == 1) continue;
			if (board[newY][newX]) continue;
			dfs(newX, newY, 0);
		}
		else if (i == 1) {
			if (dir == 0) continue;
			if (board[newY][newX]) continue;
			dfs(newX, newY, 1);
		}
		else {
			if (board[y + 1][x]) continue;
			if (board[y][x + 1]) continue;
			if (board[newY][newX]) continue;
			dfs(newX, newY, 2);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> board[i][j];
		}
	}

	dfs(2, 1, 1); // x = 열, y = 행 (r, c)
	cout << ans;
}