백준-경사로.cpp.txt

// ConsoleApplication3.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//
#include<iostream>
#include<string.h>
#include<string>
#include<queue>
#include<utility>
using namespace std;

int N;
int arr[101][101];
int L;
int result = 0;
bool visit[101][101];
void search(int rx, int ry,int xory)
{

	if (xory == 2)
	{
		if (ry == N - 1)
		{

			result++;
			return;
		}
		if (ry + 1 < N)
		{
			if (arr[rx][ry] == arr[rx][ry + 1])
			{
				search(rx, ry + 1,2);
			}
			else if (arr[rx][ry + 1]-arr[rx][ry]  == 1|| arr[rx][ry + 1] - arr[rx][ry] == -1)
			{
				if (arr[rx][ry + 1] - arr[rx][ry] == 1)
				{
					bool check = true;
					for (int i = 0; i < L; i++)
					{
						if (ry - i >= 0 && arr[rx][ry - i]+1 == arr[rx][ry+1]&&!visit[rx][ry-i])
						{
							check = true;
						}
						else
						{
							check = false;
						}
					}
					if (check)
					{
						for (int i = 0; i < L; i++)
						{
							visit[rx][ry - i] = true;
							
						}
						search(rx, ry + 1, 2);
					}
				}
				else if (arr[rx][ry + 1] - arr[rx][ry] == -1)
				{
					bool check = true;
					for (int i = 0; i < L; i++)
					{
						if (ry + (i+1) < N && arr[rx][ry +(i+1)]- arr[rx][ry] == -1 && !visit[rx][ry + (i + 1)])
						{
							check = true;
						}
						else
						{
							check = false;
						}
					}
					if (check)
					{
						for (int i = 0; i < L; i++)
						{
							visit[rx][ry + (i + 1)] = true;
						}
						search(rx, ry + 1, 2);
					}
				}
			}
			else if (arr[rx][ry + 1] - arr[rx][ry]>1)
			{
				return;
			}
		}
	}
	else if (xory == 1)
	{
		if (rx == N - 1)
		{
			result++;
			return;
		}
		if (rx + 1 < N)
		{
			if (arr[rx][ry] == arr[rx+1][ry])
			{
				search(rx+1, ry ,1);
			}
			else if (arr[rx + 1][ry]-arr[rx][ry]==1|| arr[rx + 1][ry] - arr[rx][ry] == -1)
			{
				if (arr[rx + 1][ry] - arr[rx][ry] == 1)
				{
					bool check = true;
					for (int i = 0; i < L; i++)
					{
						if (rx - i >= 0 && arr[rx-i][ry] + 1 == arr[rx+1][ry]&&!visit[rx - i][ry])
						{
							check = true;
						}
						else
						{
							check = false;
						}
					}
					if (check)
					{
						for (int i = 0; i < L; i++)
						{
							visit[rx - i][ry] = true;
							
						}
						search(rx + 1, ry, 1);
					}
				}
				else if (arr[rx + 1][ry] - arr[rx][ry] == -1)
				{

					bool check = true;
					for (int i = 0; i < L; i++)
					{
						if (rx + (i + 1) < N && arr[rx + (i + 1)][ry] - arr[rx][ry] == -1&&!visit[rx + (i + 1)][ry])
						{
							check = true;
						}
						else
						{
							check = false;
						}
					}
					if (check)
					{
						for (int i = 0; i < L; i++)
						{
							visit[rx + (i + 1)][ry] = true;
						}
						search(rx + 1, ry, 1);
					}
				}
			}
			else if (arr[rx+1][ry] - arr[rx][ry]>1)
			{
				return;
			}
		}
	}
	


}


int main()
{
	ios::sync_with_stdio(false);
	cin >> N>> L;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> arr[i][j];
			visit[i][j] = false;
		}
	}
	
	queue<pair<int, int>> q;

	q.push(make_pair(0,0));
	while (!q.empty())
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				visit[i][j] = false;
			}
		}
		int rx = q.front().first;
		int ry = q.front().second;
		q.pop();
		int ex_ry = ry;
		int ex_rx = rx;
		ry = 0;
		search(rx, ry,2);
		ry = ex_ry;
		rx = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				visit[i][j] = false;
			}
		}
		search(rx, ry,1);
		rx = ex_rx;
		
		if (rx + 1 < N)
		{
			q.push(make_pair(rx + 1, ry + 1));
		}


	}
	
	cout << result << endl;
	return 0;
}