C++ 解法, 执行用时: 124ms, 内存消耗: 680K, 提交时间: 2021-09-06 18:09:31

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m;
vector<int> ve[36];
int match[36];
bool vis[36];
char ch[36][36];
string s[36];
bool find(int x)
{
	for(auto i:ve[x])
	{
		if(vis[i])continue;
		vis[i]=1;
		if(!match[i]||find(match[i]))
		{
			match[i]=x;
			return 1;
		}
	}
	return 0;
}
void build()
{
	for(int i=1;i<=m;++i)ve[i].clear();
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		{
			int flag=1;
			for(int k=1;k<=n;++k)
			{
				if(ch[k][i]!='?'&&s[j][k-1]!='?'&&ch[k][i]!=s[j][k-1])
				{
//					cout<<i<<' '<<j<<' '<<ch[k][i]<<' '<<s[j][k-1]<<"a\n"; 
					flag=0;
					break;
				}
			}
			if(flag)
			{
//				cout<<i<<' '<<j<<"a\n";
				ve[i].push_back(j);
			}
		}
	}
}
int check()
{
	int js=0;
	memset(match,0,sizeof match);
	for(int i=1;i<=m;++i)
	{
		memset(vis,0,sizeof vis);
		if(find(i))js++;
	}
	return js;
}
int main()
{
	ios;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin>>ch[i][j];
		}
	}
	for(int i=1;i<=m;++i)cin>>s[i];
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(ch[i][j]=='?')
			{
				ch[i][j]='0';
			}
			build();
			if(check()!=m)ch[i][j]='1';
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cout<<ch[i][j];
		}
		cout<<'\n';
	}
}

C++14(g++5.4) 解法, 执行用时: 76ms, 内存消耗: 632K, 提交时间: 2020-06-09 13:29:01

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 30
#define P(x,y) (((x)-1)*m+(y))
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,a[N+5][N+5],b[N+5][N+5],ee,lnk[N+5],vis[N+5],s[N+5];struct edge {int to,nxt;}e[N*N+5];
I bool Match(CI x,CI ti)
{
	RI i;for(i=lnk[x];i;i=e[i].nxt)
	{
		if(vis[e[i].to]==ti) continue;vis[e[i].to]=ti;
		if(!s[e[i].to]||Match(s[e[i].to],ti)) return s[e[i].to]=x,1;
	}return 0;
}
I bool Check()
{
	RI i,j;for(ee=0,i=1;i<=m;++i) lnk[i]=vis[i]=s[i]=0;
	RI k;for(i=1;i<=m;++i) for(j=1;j<=m;++j)
		{for(k=1;k<=n&&(!~a[k][i]||!~b[j][k]||a[k][i]==b[j][k]);++k);k>n&&add(i,j);}
	for(i=1;i<=m;++i) if(!Match(i,i)) return 0;return 1;
}
int main()
{
	RI i,j;char op;scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) cin>>op,a[i][j]=(op=='?'?-1:(op&1));
	for(i=1;i<=m;++i) for(j=1;j<=n;++j) cin>>op,b[i][j]=(op=='?'?-1:(op&1));
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) !~a[i][j]&&(a[i][j]=0,!Check()&&(a[i][j]=1));
	for(i=1;i<=n;++i,putchar('\n')) for(j=1;j<=m;++j) putchar(a[i][j]+48);return 0;
}