백준 [17070] "파이프 옮기기 1"

무식한 방법을 통해 해결하였다. 거의 정답이 나오는데 몇 가지 반례에서는 정답이 나오지 않았다.

예)
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

문제는 가로 탐색에서 발생하였었다.
가로탐색을 하기 위해서는 그전 파이프의 모양을 세로는 허용하지 않아야 한다는 점을 간과하였고 이를 해결하기 위해 세로 여부를 파악하는 l을 탐색조건으로 넣어 해결하였다. 다른 사람들에 비해 가시성은 좋지 않은 점이 아쉽다.

#include <iostream>
#include <deque>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <map>
#include <cstring>

using namespace std;
int n, result = 0;
int house[18][18];

int turn = 0;

void pi(int x, int y, int turn, int l) {
	if (x == n - 1 && y == n - 1) {
		result++;
		return;
	}
	//가로
	if (house[x][y + 1] == 0 && x < n && y < n && l == 0) {
		pi(x, y + 1, 0, 0);
	}
	//세로 -> 세로
	if (house[x + 1][y] == 0 && x + 1 < n && y < n && l == 1) {
		pi(x + 1, y, 0, 1);
	}
	//대각선 -> 세로
	if (house[x + 1][y] == 0 && x + 1 < n && y < n && turn == 1) {
		pi(x + 1, y, 0, 1);
	}
	//대각선
	if (house[x + 1][y + 1] == 0 && house[x][y + 1] == 0 && house[x + 1][y] == 0 && x + 1 < n && y + 1 < n) {
		pi(x + 1, y + 1, 1, 0);
	}

}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> house[i][j];
		}
	}
	pi(0, 1, 0, 0);

	cout << result;

	return 0;

}