20分求助
查看原帖
20分求助
200116
dshzsh楼主2020/8/6 14:52
#include<bits/stdc++.h>
using namespace std;
int mp[20][20];
long long dp[2][(1<<14)];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		string x;
		cin>>x;
		for(int j=1;j<=m;j++)
			if(x[j-1]=='*')
				mp[i][j]=1;
	}
	int d=0;
	dp[d][0]=1;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			d=!d;
			memset(dp[d],0,sizeof(dp[d]));
			if(j!=n)
			for(int s=0;s<(1<<(n+1));s++)
			{
				bool z=(s&(1<<(j-1))),y=(s&(1<<(j)));
				if(mp[i][j])
					if(z==0&&y==0)//O
						dp[d][s]+=dp[!d][s];
				else
				{
					if(z==0&&y==0)//上面和左边都不想插 
						dp[d][s|(1<<(j-1))|(1<<j)]+=dp[!d][s];
					if(z==1&&y==0)//左边想插
					{
						dp[d][s]+=dp[!d][s];
						dp[d][s^(1<<(j-1))|(1<<j)]+=dp[!d][s];
					}
					if(z==0&&y==1)//上面想插
					{
						dp[d][s]+=dp[!d][s];
						dp[d][s^(1<<j)|(1<<(j-1))]+=dp[!d][s];
					}
					if(z==1&&y==1)//都想插
						dp[d][s^(1<<j)^(1<<(j-1))]+=dp[!d][s];
				}
			}
			if(j==n)
			for(int s=0;s<(1<<(n+1));s++)
			{
				bool z=(s&(1<<(j-1))),y=(s&(1<<(j)));
				if(mp[i][j])
					if(z&&y)//O
						dp[d][(s>>1)]+=dp[!d][s];
				else
				{
					//都不想插就完了 
					if(z==1&&y==0)//左边想插
						dp[d][s>>1]+=dp[!d][s];
					if(z==0&&y==1)//上面想插
						dp[d][(s^(1<<j)|(1<<(j-1)))>>1]+=dp[!d][s];
					if(z==1&&y==1)//都想插
						dp[d][(s^(1<<j)^(1<<(j-1)))>>1]+=dp[!d][s];
				}
			}
		}
	printf("%d",dp[d][0]);
	return 0;
}

好像我的程序只会输出0

2020/8/6 14:52
加载中...