Submission #924952

#	Time	Username	Problem	Language	Result	Execution time	Memory
924952		Faisal_Saqib	Plus Minus (BOI17_plusminus)	C++17	0 / 100	0 ms	348 KiB

plusminus

#include <iostream>
#include <map>
#include <bitset>
using namespace std;
char g[10][10];
int n,m;
int ind(int i,int j)
{
	return (i*(m-1))+j;
}
int val(char c)
{
	return ((c=='+')?1:-1);
}
map<string,bool> posp;
void backtrack(int i,int j)
{
	if(i==n and j==0)
	{
		string s;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++)
			{
				s+=g[i][j];
			}
		}
		posp[s]=1;
		return;
	}
	// if(i>=n or j>=m or i<0 or j<0)
	// 	return;
	if(g[i][j]=='?')
	{
		for(char a:{'+','-'})
		{
			g[i][j]=a;
			if(i>0 and j>0)
			{
				int su=val(g[i][j-1])+val(g[i][j])+val(g[i-1][j])+val(g[i-1][j-1]);
				if(su!=0)
				{
					continue;
				}
			}
			if((j==(m-1)))
			{
				backtrack(i+1,0);
			}
			else
			{
				backtrack(i,j+1);
			}
		}
		g[i][j]='?';
	}
	else
	{
			if((j==(m-1)))
			{
				backtrack(i+1,0);
			}
			else
			{
				backtrack(i,j+1);
			}
	}
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	int k;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			g[i][j]='?';
	for(int j=0;j<k;j++)
	{
		char c;
		cin>>c;
		int x,y;
		cin>>x>>y;
		x--;y--;
		g[x][y]=c;
	}
	// int ans=0;
	// int lt=n*m;
	// int pw=(1<<lt);
	// for(int mask=0;mask<pw;mask++)
	// {
	// 	bool pos=1;
	// 	// (i,j) = (i*m)+j
	// 	// cout<<"Grid "<<mask<<endl;
	// 	for(int i=0;pos and i<n;i++)
	// 	{
	// 		for(int j=0;j<m;j++)
	// 		{
	// 			char f=(((mask&(1<<ind(i,j)))>0)?'+':'-');
	// 			// cout<<f<<' ';
	// 			if(f!=g[i][j] and g[i][j]!='?')
	// 			{
	// 				pos=0;
	// 				break;
	// 			}
	// 		}
	// 		// cout<<endl;
	// 	}
	// 	// cout<<"endl"<<endl;
	// 	if(!pos)
	// 		continue;
	// 	for(int i=1;i<n and pos;i++)
	// 	{
	// 		for(int j=1;j<m;j++)
	// 		{
	// 			int f=(((mask&(1<<ind(i-1,j-1)))>0)?1:-1);
	// 			int s=(((mask&(1<<ind(i-1,j)))>0)?1:-1);
	// 			int f1=(((mask&(1<<ind(i,j-1)))>0)?1:-1);
	// 			int s1=(((mask&(1<<ind(i,j)))>0)?1:-1);
	// 			if((f+s+f1+s1)!=0)
	// 			{
	// 				pos=0;
	// 				break;
	// 			}
	// 		}
	// 	}
	// 	if(!pos)
	// 		continue;
	// 	// cout<<"Grid "<<mask<<endl;
	// 	// for(int i=0;pos and i<n;i++)
	// 	// {
	// 	// 	for(int j=0;j<m;j++)
	// 	// 	{
	// 	// 		char f=(((mask&(1<<ind(i,j)))>0)?'+':'-');
	// 	// 		cout<<f<<' ';
	// 	// 	}
	// 	// 	cout<<endl;
	// 	// }
	// 	// cout<<"endl"<<endl;
	// 	ans++;
	// }
	// cout<<ans<<'\n';
	backtrack(0,0);
	cout<<posp.size()<<endl;
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46