3-O 사다리 조작 / 예제 입력에 따른 출력 결과는 맞는데 계속 시간초과가 납니다.

안녕하세요 선생님. 코딩테스트 강의 잘 듣고 있습니다.
15684번 문제 코드를 짰는데, 답 코드랑 비교해서 로직은 맞는 것 같은데 자꾸 시간초과가 납니다.
이유를 잘 모르겠어서 질문 드립니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int H, W, P;
bool isGaro[12][12][32]; //[시작점][끝점][가로선을 놓을 수 있는 위치]
int ans = 4; //최대값 3보다 높은 값으로 초기화

bool check()
{
	for (int i = 1; i <= H; i++) {
		int now = i;
		for (int j = 1; j <= P; j++) {

			//자신 기준으로 오른쪽에 선이 있음
			if (isGaro[now][now + 1][j]) {
				now++; //오른쪽으로 이동
				continue;
			}

			//자신 기준으로 왼쪽에 선이 있음
			if (isGaro[now - 1][now][j]) {
				now--; //왼쪽으로 이동
				continue;
			}

		}

		if (now != i) {
			//한번이라도 번호가 다르면 실패
			return false;
		}
	}

	return true;
}



void go(int pos ,int garoCnt)
{
	//만약 현재 갱신된 가로선 개수보다 개수가 많으면 바로 종료
	if (ans <= garoCnt || garoCnt > 3 ) return;

	//현재 모든 세로선이 사다리 게임을 진행했을 때
	//같은 번호가 나오는 지 체크
	
	//만약 모두 같은 번호가 나오면
	//갯수 갱신한 뒤에 종료
	if (check()) {
		ans = min(ans, garoCnt);
		return;
	}
	

	//세로선 번호
	int s = pos / 1000;
	//가로선 번호
	int p = pos % 1000;


	//만약 s == H이면
	//다음 가로선으로 넘어가기
	//cout << "세로선 번호 : " << s << ' ' << "가로선 번호 : " << p << '\n';

	for (int i = p; i <= P; i++) {
		for (int j = 1; j <= H; j++) {

			//현재 위치에 있는 가로선을 추가함
			if (!isGaro[j][j + 1][i] && !isGaro[j-1][j][i] && !isGaro[j][j][i]) {
				isGaro[j][j + 1][i] = true;

				go(1000 * (j + 1) + p, garoCnt + 1);

				isGaro[j][j + 1][i] = false;
			}
		}
	}
	

	


}

int main(int argc, char** argv) {
	cin >> H >> W >> P;
	for (int i = 0; i < W; i++) {
		int a, b;
		cin >> a >> b;
		isGaro[b][b + 1][a] = true; //b번 세로선과 b+1번 세로선을 a번 점선위치에서 연결
	
	}

	//만약 놓여져 있는 가로선이 없다면
	//0을 출력
	if (W == 0) {
		cout << 0;
		return 0;
	}

	//1000 / 1000 = s 
	//1000 % 1000 = p
	//1000 * s + p
	
	//세로선과 가로선 모두 1,1에서 시작
	go(1000* 1 + 1,0);
	
	if (ans >= 4) {
		cout << -1;
	}
	else cout << ans;

}

	for (int i = p; i <= P; i++) {
		for (int j = (i == p) ? s : 1; j < H; j++) {

			//현재 위치에 있는 가로선을 추가함
			if (!isGaro[j][j + 1][i] && !isGaro[j-1][j][i] && !isGaro[j][j][i]) {
				isGaro[j][j + 1][i] = true;