打模板的经验：
1.变量名取一样，换行也一样，不要宏定义
2.大小写，少写，大括号
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#include<ctime>
#include<stack>
#include<map>
#include<set>
#include<list>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
//#define x first
//#define y second typedef double db;
typedef long long ll; const int MAXD = 15;
const int STATE = 1e6 + 5;
const int HASH = 3e5 + 7;
const int MOD = 1e9 + 7;
int N, M, K;
int maze[MAXD][MAXD];
int code[MAXD];
int ch[MAXD];
int num;
struct HASHMAP
{
int head[HASH], next[STATE], size;
ll state[STATE];
int f[STATE];
void init()
{
size = 0;
mmm(head, -1);
}
void push(ll st, int ans)
{
int i;
int h = st % HASH;
for (i = head[h]; i != -1; i = next[i])
if (state[i] == st)
{
f[i] += ans;
f[i] %= MOD;
return;
}
state[size] = st;
f[size] = ans;
next[size] = head[h];
head[h] = size++;
}
}hm[2];
void decode(int *code, int m, long long st)
{
num = st & 63;
st >>= 6;
for (int i = m; i >= 0; i--)
{
code[i] = st & 7;
st >>= 3;
}
}
ll encode(int *code, int m)
{
int cnt = 1;
mmm(ch, -1);
ch[0] = 0;
ll st = 0;
rep(i, 0, m)
{
if (ch[code[i]] == -1)ch[code[i]] = cnt++;
code[i] = ch[code[i]];
st <<= 3;
st |= code[i];
}
st <<= 6;
st |= num;
return st;
}
void shift(int *code, int m)
{
for (int i = m; i > 0; i--)code[i] = code[i - 1];
code[0] = 0;
}
void dpblank(int i, int j, int cur)
{
int k, left, up;
for (k = 0; k < hm[cur].size; k++)
{
decode(code, M, hm[cur].state[k]);
left = code[j - 1];
up = code[j];
if (left&&up)
{
if (left == up)
{
if (num >= K)continue;
int t = 0; for (int p = 0; p < j - 1; p++)
if (code[p])t++;
if (t & 1)continue;
if (num < K)
{
num++;
code[j - 1] = code[j] = 0;
hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);
}
}
else
{
code[j - 1] = code[j] = 0;
for (int t = 0; t <= M; t++)
if (code[t] == up)
code[t] = left;
hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);
}
}
else if (left || up)
{
int t;
if (left) t = left;
else t = up;
if (maze[i][j + 1])
{
code[j - 1] = 0;
code[j] = t;
hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]);
}
if (maze[i + 1][j])
{
code[j] = 0;
code[j - 1] = t;
hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);
}
}
else
{
if (maze[i][j + 1] && maze[i + 1][j])
{
code[j - 1] = code[j] = 13;
hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);
}
}
}
}
void dplock(int i, int j, int cur)
{
int k;
for (k = 0; k < hm[cur].size; k++)
{
decode(code, M, hm[cur].state[k]);
code[j - 1] = code[j] = 0;
hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);
}
}
char str[20];
void init()
{
cin >> N >> M >> K;
mmm(maze, 0);
rep(i, 1, N)
{
scanf("%s", &str);
for (int j = 1; j <= M; j++)
if (str[j - 1] == '.')
maze[i][j] = 1;
}
}
void solve()
{
int cur = 0;
hm[cur].init();
hm[cur].push(0, 1);
rep(i, 1, N)
rep(j, 1, M)
{
hm[cur ^ 1].init();
if (maze[i][j])dpblank(i, j, cur);
else dplock(i, j, cur);
cur ^= 1;
}
int ans = 0;
for (int i = 0; i < hm[cur].size; i++)
if (hm[cur].state[i] == K)
{
ans += hm[cur].f[i];
ans %= MOD;
}
printf("%d\n", ans); }
int main()
{
int t;
cin >> t;
while (t--)
{
init();
solve();
}
//cin >> t;
}
/*
2
4 4 1
**..
....
....
....
4 1
....
....
....
....
*/
/*
HDU 4285
要形成刚好K条回路的方法数
要避免环套环的情况。
所以形成回路时，要保证两边的插头数是偶数 G++ 11265ms 11820K
C++ 10656ms 11764K */ #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std; const int MAXD=;
const int STATE=;
const int HASH=;//这个大一点可以防止TLE,但是容易MLE
const int MOD=; int N,M,K;
int maze[MAXD][MAXD];
int code[MAXD];
int ch[MAXD];
int num;//圈的个数
struct HASHMAP
{
int head[HASH],next[STATE],size;
long long state[STATE];
int f[STATE];
void init()
{
size=;
memset(head,-,sizeof(head));
}
void push(long long st,int ans)
{
int i;
int h=st%HASH;
for(i=head[h];i!=-;i=next[i])
if(state[i]==st)
{
f[i]+=ans;
f[i]%=MOD;
return;
}
state[size]=st;
f[size]=ans;
next[size]=head[h];
head[h]=size++;
}
}hm[];
void decode(int *code,int m,long long st)
{
num=st&;
st>>=;
for(int i=m;i>=;i--)
{
code[i]=st&;
st>>=;
}
}
long long encode(int *code,int m)//最小表示法
{
int cnt=;
memset(ch,-,sizeof(ch));
ch[]=;
long long st=;
for(int i=;i<=m;i++)
{
if(ch[code[i]]==-)ch[code[i]]=cnt++;
code[i]=ch[code[i]];
st<<=;
st|=code[i];
}
st<<=;
st|=num;
return st;
}
void shift(int *code,int m)
{
for(int i=m;i>;i--)code[i]=code[i-];
code[]=;
}
void dpblank(int i,int j,int cur)
{
int k,left,up;
for(k=;k<hm[cur].size;k++)
{
decode(code,M,hm[cur].state[k]);
left=code[j-];
up=code[j];
if(left&&up)
{
if(left==up)
{
if(num>=K)continue;
int t=;
//要避免环套环的情况，需要两边插头数为偶数
for(int p=;p<j-;p++)
if(code[p])t++;
if(t&)continue;
if(num<K)
{
num++;
code[j-]=code[j]=;
hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);
}
}
else
{
code[j-]=code[j]=;
for(int t=;t<=M;t++)
if(code[t]==up)
code[t]=left;
hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);
}
}
else if(left||up)
{
int t;
if(left)t=left;
else t=up;
if(maze[i][j+])
{
code[j-]=;
code[j]=t;
hm[cur^].push(encode(code,M),hm[cur].f[k]);
}
if(maze[i+][j])
{
code[j]=;
code[j-]=t;
hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);
}
}
else
{
if(maze[i][j+]&&maze[i+][j])
{
code[j-]=code[j]=;
hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);
}
}
}
}
void dpblock(int i,int j,int cur)
{
int k;
for(k=;k<hm[cur].size;k++)
{
decode(code,M,hm[cur].state[k]);
code[j-]=code[j]=;
hm[cur^].push(encode(code,j==M?M-:M),hm[cur].f[k]);
}
}
char str[];
void init()
{
scanf("%d%d%d",&N,&M,&K);
memset(maze,,sizeof(maze));
for(int i=;i<=N;i++)
{
scanf("%s",&str);
for(int j=;j<=M;j++)
if(str[j-]=='.')
maze[i][j]=;
}
}
void solve()
{
int i,j,cur=;
hm[cur].init();
hm[cur].push(,);
for(i=;i<=N;i++)
for(j=;j<=M;j++)
{
hm[cur^].init();
if(maze[i][j])dpblank(i,j,cur);
else dpblock(i,j,cur);
cur^=;
}
int ans=;
for(i=;i<hm[cur].size;i++)
if(hm[cur].state[i]==K)
{
ans+=hm[cur].f[i];
ans%=MOD;
}
printf("%d\n",ans); }
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
init();
solve();
}
return ;
} /*
Sample Input
4 4 1
**..
....
....
....
4 1
....
....
....
.... Sample Output
6 */
#include<algorithm>#include<iostream>#include<stdlib.h>#include<string.h>#include<math.h>#include<stdio.h>#include<vector>#include<queue>#include<string>#include<ctime>#include<stack>#include<map>#include<set>#include<list>using namespace std;#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)#define per(i,j,k) for(int i = (int)j;i >= (int)k;i --)#define debug(x) cerr<<#x<<" = "<<(x)<<endl#define mmm(a,b) memset(a,b,sizeof(a))#define pb push_back//#define x first//#define y second
typedef double db;typedef long long ll;
const int MAXD = 15;const int STATE = 1e6 + 5;const int HASH = 3e5 + 7;const int MOD = 1e9 + 7;int N, M, K;int maze[MAXD][MAXD];int code[MAXD];int ch[MAXD];int num;struct HASHMAP{int head[HASH], next[STATE], size;ll state[STATE];int f[STATE];void init(){size = 0;mmm(head, -1);}void push(ll st, int ans){int i;int h = st % HASH;for (i = head[h]; i != -1; i = next[i])if (state[i] == st){f[i] += ans;f[i] %= MOD;return;}state[size] = st;f[size] = ans;next[size] = head[h];head[h] = size++;}}hm[2];void decode(int *code, int m, long long st){num = st & 63;st >>= 6;for (int i = m; i >= 0; i--){code[i] = st & 7;st >>= 3;}}ll encode(int *code, int m){int cnt = 1;mmm(ch, -1);ch[0] = 0;ll st = 0;rep(i, 0, m){if (ch[code[i]] == -1)ch[code[i]] = cnt++;code[i] = ch[code[i]];st <<= 3;st |= code[i];}st <<= 6;st |= num;return st;}void shift(int *code, int m){for (int i = m; i > 0; i--)code[i] = code[i - 1];code[0] = 0;}void dpblank(int i, int j, int cur){int k, left, up;for (k = 0; k < hm[cur].size; k++){decode(code, M, hm[cur].state[k]);left = code[j - 1];up = code[j];if (left&&up){if (left == up){if (num >= K)continue;int t = 0;
for (int p = 0; p < j - 1; p++)if (code[p])t++;if (t & 1)continue;if (num < K){num++;code[j - 1] = code[j] = 0;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else{code[j - 1] = code[j] = 0;for (int t = 0; t <= M; t++)if (code[t] == up)code[t] = left;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else if (left || up){int t;if (left) t = left;else t = up;if (maze[i][j + 1]){code[j - 1] = 0;code[j] = t;hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]);}if (maze[i + 1][j]){code[j] = 0;code[j - 1] = t;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}else{if (maze[i][j + 1] && maze[i + 1][j]){code[j - 1] = code[j] = 13;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}}}void dplock(int i, int j, int cur){int k;for (k = 0; k < hm[cur].size; k++){decode(code, M, hm[cur].state[k]);code[j - 1] = code[j] = 0;hm[cur ^ 1].push(encode(code, j == M ? M - 1 : M), hm[cur].f[k]);}}char str[20];void init(){cin >> N >> M >> K;mmm(maze, 0);rep(i, 1, N){scanf("%s", &str);for (int j = 1; j <= M; j++)if (str[j - 1] == '.')maze[i][j] = 1;}}void solve(){int cur = 0;hm[cur].init();hm[cur].push(0, 1);rep(i, 1, N)rep(j, 1, M){hm[cur ^ 1].init();if (maze[i][j])dpblank(i, j, cur);else dplock(i, j, cur);cur ^= 1;}int ans = 0;for (int i = 0; i < hm[cur].size; i++)if (hm[cur].state[i] == K){ans += hm[cur].f[i];ans %= MOD;}printf("%d\n", ans);
}int main(){int t;cin >> t;while (t--){init();solve();}//cin >> t;}/*24 4 1**..............4 1................*/