ProblemSolving/1189.cpp at master · mimseong/ProblemSolving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int ans = 0;
int n, m, k;

int xv[] = { 1, 0, -1, 0 };
int yv[] = { 0, 1, 0, -1 };

bool visited[30][30];
char mapv[30][30];

void	func(int x, int y, int cnt)
{
	//printf("%d %d %d\n", x, y, cnt);
	if (x == 0 && y == m - 1)
	{
		//printf("!\n");
		if (cnt == k)
			ans++;
		return;
	}


	visited[x][y] = true;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + xv[i];
		int ny = y + yv[i];

		if (nx < 0 || n <= nx || ny < 0 || m <= ny)
			continue;

		if (mapv[nx][ny] == 'T' || visited[nx][ny])
			continue;

		func(nx, ny, cnt + 1);
	}

	visited[x][y] = false;
}

int     main()
{
	scanf("%d %d %d", &n, &m, &k);

	char tmp;
	scanf("%c", &tmp);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			scanf("%c", &mapv[i][j]);
		scanf("%c", &tmp);
	}

	func(n - 1, 0, 1);
	printf("%d\n", ans);

	return 0;
}