This code uses too much time that I get TLEs.

And here is the problem:

FM opened the photo album and recalled his childhood...

It was a crazy night, and the dormitory inspector was still making his rounds. FM's school dormitory can be abstracted as a rectangle of size $$$N \times M$$$. Strangely, the dormitories are connected on all four sides, meaning that dormitory $$$A_{i,j}$$$ is directly connected to dormitories $$$A_{i,j-1}$$$, $$$A_{i,j+1}$$$, $$$A_{i-1,j}$$$, and $$$A_{i+1,j}$$$. However, some rooms are locked, and even FM doesn't know what's going on inside. We'll represent these rooms with an x. Conversely, if a dormitory is accessible, it will be represented by a ..

The dormitory inspector's time is very precious, and he doesn't want to pass through the same dormitory more than once, as that would be pointless. He must eventually return to the first dormitory he inspected, and of course, every dormitory must be checked. However, to ensure that he doesn't pass through the same dormitory multiple times, the inspector can open the doors of x dormitories at most $$$k$$$ times.

Now, at the request of his roommate JW, FM needs to calculate how many ways the dormitory inspector can carry out his inspection. If the inspector cannot complete his rounds normally, the output should be NO. In any case, the dormitory inspector must ensure that his route is maximized.

The input consists of $$$N+1$$$ lines:

The first line contains $$$3$$$ positive integers $$$N, M, k$$$, representing the size of the dormitory rectangle.

The next $$$N$$$ lines each contain $$$M$$$ positive integers $$$A_{i,j}$$$, indicating the type of each dormitory, which can only be either . or x.

The output consists of only $$$1$$$ line:

If there is a possibility, output $$$1$$$ integer representing the number of possible inspection routes (since the data is large, please take the result modulo $$$100,000,007$$$);

Otherwise, output the string NO to indicate that there is no possibility.

Note: The number of ways refers to the count of essentially different cyclic routes; if there is only one accessible dormitory, also output NO.

Data Range

For all test data, the following guarantees apply:

• $$$1 \leq N, M \leq 12$$$, $$$1 \leq k \leq N \times M$$$

Special Property A: All $$$A_{i,j}$$$ are ..

The test cases are equally weighted.

Sample Explanation

1.in:

4 4 1

....

....

....

....

1.out:

6

2.in:

12 12 1

............

............

xxxxxxxxxx.x

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxxxxxx

2.out:

1

3.in:

1 1 1

x

3.out: NO

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 100000007;
map<int,int> f[2];
int n,m,s,t,k,ans;
bool mp[15][15];
int pos(int v,int x){return (v << (x << 1));}
int solve(){
	int now = 0,nxt = 1;
	f[0][0] = 1;
	int U = (1LL << ((m + 1) << 1)) - 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			f[nxt].clear();
			for(auto k : f[now]){
				int S = k.first,val = k.second;
				int L = (S >> ((j - 1) << 1)) & 3,R = (S >> (j << 1)) & 3;
				if(!mp[i][j]){
					if(!L && !R) f[nxt][S] += val;
					continue;
				}
				if(!L && !R){
					if(mp[i][j + 1] && mp[i + 1][j]) f[nxt][S ^ pos(1,j - 1) ^ pos(2,j)] += val;
				}
				else if(L == 2 && R == 1) f[nxt][S ^ pos(L,j - 1) ^ pos(R,j)] += val;
				else if(!L || !R) {
					if(!L){
						if(mp[i][j + 1]) f[nxt][S] += val;
						if(mp[i + 1][j]) f[nxt][S ^ pos(L,j - 1) ^ pos(L,j) ^ pos(R,j - 1) ^ pos(R,j)] += val;
					}else if(!R){
						if(mp[i][j + 1]) f[nxt][S ^ pos(L,j - 1) ^ pos(L,j) ^ pos(R,j - 1) ^ pos(R,j)] += val;
						if(mp[i + 1][j]) f[nxt][S] += val;
					}
				}
				else if(L == R){
					if(L == 1){
						int du = 0;
						for(int p = j;;p++){
							int o = (S >> (p << 1)) & 3;
							if(o == 1) du++;
							if(o == 2) du--;
							if(!du){
								f[nxt][S ^ pos(L,j - 1) ^ pos(R,j) ^ pos(2,p) ^ pos(1,p)] += val;
								break;
							}
						}
					}else if(L == 2){
						int du = 0;
						for(int p = j - 1;;p--){
							int o = (S >> (p << 1)) & 3;
							if(o == 1) du--;
							if(o == 2) du++;
							if(!du){
								f[nxt][S ^ pos(L,j - 1) ^ pos(R,j) ^ pos(2,p) ^ pos(1,p)] += val;
								break;
							}
						}
					}
				}
				else if(L == 1 && R == 2 && i == s && j == t) return val;
			}
			swap(now,nxt);
		}
		f[nxt].clear();
		for(auto k : f[now]) f[nxt][(k.first << 2) & U] += k.second;
		swap(now,nxt);
	}
	return 0;
}
void dfs(int x){
    if(x > k) return;
    ans = max(ans,solve() % M);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(mp[i][j] == 0){
                mp[i][j] = 1;
                dfs(x + 1);
                mp[i][j] = 0;
            }
        }
    }
    return;
}
signed main(){
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
            char tmp; cin >> tmp;
			mp[i][j] = tmp == '.';
			if(mp[i][j]){
                s = i;
                t = j;
            }
		}
    }
    if(s == 0){
        s = n;
        t = m;
    }
    dfs(0);
    if(ans > 0) printf("%lld",ans % M);
    else cout << "NO";
	return 0;
}