Submission #924953

#	Time	Username	Problem	Language	Result	Execution time	Memory
924953		Faisal_Saqib	Plus Minus (BOI17_plusminus)	C++17	12 / 100	3 ms	604 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(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)
				{
					return;
				}
			}
			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;
	}
	backtrack(0,0);
	cout<<posp.size()<<endl;
	return 0;
}

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