C++ 解法, 执行用时: 218ms, 内存消耗: 28920K, 提交时间: 2021-12-27 19:32:24

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Con continue
using namespace std;
const int mod=1e9+7,N=20,SS=(1<<15);
int s[N][N],f[N][N][SS],n,m,x[N<<1],y[N<<1],k,a[N][N];
int work(int l,int r){return ((1<<r)-1)^((1<<(l-1))-1);}
bool chk(int X,int Y,int i,int S){
	if(Y+y[i]>m)return 0;
	if(X+x[i]-1>n)return 0;
	if(work(Y+1,Y+y[i])&S)return 0;
	bool ff=(s[X][Y+y[i]]-s[X][Y]==y[i]);
	if(x[i]==2)ff&=(s[X+1][Y+y[i]]-s[X+1][Y]==y[i]);
	return ff;
}
void add(int &x,int y){x=(x+y)%mod;}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    For(i,1,n)For(j,1,m){
        scanf("%d",&a[i][j]);
        s[i][j]=a[i][j]+s[i][j-1];
    }
    For(i,1,k)scanf("%d%d",&x[i],&y[i]);
    f[1][0][0]=1;
    For(i,1,n)For(j,0,m)For(S,0,(1<<m)-1){
        if(!f[i][j][S])Con;
        if(j==m){add(f[i+1][0][S],f[i][j][S]);Con;}
        if(!a[i][j+1]){add(f[i][j+1][S],f[i][j][S]);Con;}
        if(S&(1<<j)){add(f[i][j+1][S^(1<<j)],f[i][j][S]);Con;}
        add(f[i][j+1][S],f[i][j][S]);
        For(p,1,k){
            if(!chk(i,j,p,S))Con;
            if(x[p]==1)add(f[i][j+y[p]][S&(((1<<m)-1)^work(j+1,j+y[p]))],f[i][j][S]);
            else add(f[i][j+y[p]][S|work(j+1,j+y[p])],f[i][j][S]);
        }
    }
    printf("%d",f[n][m][0]);
}