#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
