삽질하느라 디버깅한다고 che2를 매번 확인하면서 깨달은게 있다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <limits.h>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
int dx[] = { 0,1 };
int dy[] = { 1,0 };
//int tb1[100001];
ll tb2[20][20];
//int che[100001];
ll che2[20][20];
//int sum[1001];
int n, m;
//int min3(int a,int b,int c){
// a = (a < b ? a : b);
// return (a < c ? a : c);
//}
int aaa, bbb;
ll go(int s, int e, int fx, int fy) {
if (che2[s][e] != -1) {
return che2[s][e];
}
if (s == fx && e == fy) {
return che2[s][e] = 1;
}
che2[s][e] = 0;
ll& ret = che2[s][e];
for (int k = 0; k < 2; ++k) {
int nx = dx[k] + s;
int ny = dy[k] + e;
if (aaa <= nx && nx <= fx && bbb <= ny && ny <= fy) {
ret += go(nx, ny, fx, fy);
}
}
return ret;
}
int main(void)
{
int n, m,k;
cin >> n >> m >> k;
int a, b;
bool ans_is_easy = false;
if (k == 0) {
ans_is_easy = true;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
tb2[i][j] = (i - 1)*m + j;
if ((i-1)*m+j == k && ans_is_easy == false) {
a = i, b = j;
}
}
}
//cout << "a b " << a << ' ' << b << endl;
aaa = 1;
bbb = 1;
memset(che2, -1, sizeof(che2));
ll kk;
if (!ans_is_easy) {
kk = go(1, 1, a, b);
}
/*for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cout << che2[i][j] << ' ';
}
cout << endl;
}*/
memset(che2, -1, sizeof(che2));
ll kkk;
if (ans_is_easy) {
cout << go(1, 1, n, m);
return 0;
}
else {
aaa = a;
bbb = b;
kkk = go(a, b, n, m);
}
//for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= m; ++j) {
// cout << che2[i][j] << ' ';
// }
// cout << endl;
//}
cout << kk * kkk;
return 0;
}