lives （ 状态压缩 + dfs ）（广工19年寒假集训 - 组队）

补得有点难受。。感觉我好菜 = =、

题目传送门

题目

题意
大概就是 n * m 的矩阵里有些生命 。。。 题意题目都有说了，不讲了

思路
因为 n 和 m 很小，就想到可以先把答案全部求出来。然后因为数据很小，所以考虑一下状压，用n*m位二进制来存储，每一位上表示一个1x1的小方格，然后1表示有生命，0表示没有生命，如果这种状态在当前 n = i ，m = j 下没有被搜索过（ vis[k] == -1 ），那么开始dfs。

dfs d的是在当前状态的后一天的状态，用tmp来存储
if( now & (1<<(im+j)) ) 表示后一天( i , j ) 位置上有个生命，按照题意，开始八方位搜索，统计这八方位的生命的个数，如果可以，则 tmp |= (1<<(im+j))，表示记录后一天（ i , j ）上有生命
else 的话，则表示后一天( i , j ) 位置上没有生命，然后同上。

如果所有格子遍历完之后，都没有一个生命的（tmp==0），就vis[now] = 0，如果有，则返回vis[now] = dfs(tmp)，搜后一天状态的后一天状态是否可以，如果vis[tmp]!=-1，其答案就是vis[tmp]，否则继续下一天。

代码

#include  <algorithm>//           ¨|¨|¨|        ¨|¨|¨|¨|
#include   <iostream>//         ¨}¨}¨}¨}      ¨~¨~¨~
#include    <cstring>//        ¨~¨~ ¨~¨~    ¨~¨~
#include    <stdio.h>//       ¨~¨~  ¨~¨~   ¨~¨~
#include     <vector>//      ¨~¨~   ¨~¨~  ¨~¨~
#include      <cmath>//     ¨~¨~    ¨~¨~  ¨~¨~
#include      <queue>//    ¨~¨~ ¨~¨~¨~¨~  ¨~¨~
#include        <map>//   ¨~¨~      ¨~¨~   ¨~¨~
using namespace std ;//  ¨~¨~       ¨~¨~    ¨~¨~¨~
typedef long long ll;// ¨~¨~        ¨~¨~      ¨~¨~¨~¨~¨~
#define pi pair<int,int>  ///////////////////////////////
#define P(x,y) make_pair(x,y)
const int maxn = 1<<(5*5+1);
const ll mod = 998244353;
ll read()
{
	ll x=0;char ch=getchar(); bool flag = false;
	if(ch=='-') { flag = true; ch = getchar();}
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	if(flag) return -x;  else return x;
}
////////////////////////////////////////////////////////////
/*
int n,m,dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
int vis[maxn],ans[6][6];
int dfs(int now){
    if(vis[now]!=-1) return vis[now];
    vis[now]=1;
    int tmp = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int cnt = 0;
            if( now & (1<<(i*m+j)) ){
                for(int k=0;k<8;k++){
                    int x = i + dx[k], y = j + dy[k];
                    if( x>=0 && y>=0 && x<n && y<m )
                        cnt += (now&(1<<(x*m+y)))>0;
                }
                if( cnt == 2 || cnt == 3 ) tmp |= (1<<(i*m+j));
            }else{
                for(int k=0;k<8;k++){
                    int x = i + dx[k], y = j + dy[k];
                    if( x>=0 && y>=0 && x<n && y<m )
                        cnt += (now&(1<<(x*m+y)))>0;
                }
                if( cnt == 3 ) tmp |= (1<<(i*m+j));
            }
        }
    }
    if(tmp==0) return vis[now] = 0;
    else return vis[now] = dfs(tmp);
}*/
int ans[5][5] = {
0,0,0,0,0,0,5,18,73,267,0,18,150,1533,11398,0,73,1533,31828,469972,0,267,11398,469972,12785753
};
////////////////////////////////////////////////////////////
int main()
{   if(fopen("in.txt","r")) freopen("in.txt","r",stdin);
    int T,n,m,k,i,sum,j,t,tmp;
    /*
    for(i=1;i<=5;i++)
        for(j=1;j<=5;j++){
            n = i; m = j;
            memset(vis,-1,sizeof(vis));
            for(k=0;k<(1<<(n*m));k++){
                if(vis[k]==-1) dfs(k);
                ans[n][m] += vis[k];
            }
            printf("%d,",ans[i][j]);
        }
    */
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",ans[n-1][m-1]);
    }
    return 0;
}