NC24121. [USACO 2011 Nov G]Binary Sudoku
描述
输入描述
* Lines 1..9: Each line contains a 9-digit binary string corresponding
to one row of the initial game board.
输出描述
* Line 1: The minimum number of toggles required to make every row,
column, and subgrid have even parity.
示例1
输入:
000000000 001000100 000000000 000110000 000111000 000000000 000000000 000000000 000000000
输出:
3
说明:
The Sudoku board in the sample input is the same as in the problem text above.C++14(g++5.4) 解法, 执行用时: 821ms, 内存消耗: 408K, 提交时间: 2020-10-18 17:03:55
#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const int N=10;
int v[N][N]={
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
};
int a[N][N],X[N],Y[N],g[N];
int n,m,ans=1e9;
char c;
void dfs(int x,int y,int sum){
if(sum>=ans)return;
if(y>9){
if(++m==1e7+5e6){printf("%d",ans);exit(0);}
x++;y=1;
if(X[x-1]&1)return;
if(x==4)if((g[1]&1)||(g[2]&1)||(g[3]&1))return;
if(x==7)if((g[4]&1)||(g[5]&1)||(g[6]&1))return;
if(x==10){
if((g[7]&1)||(g[8]&1)||(g[9]&1))return;
for(int i=1;i<=9;i++)if(Y[i]&1)return;
ans=sum;return;
}
}
dfs(x,y+1,sum);
X[x]++;Y[y]++;g[v[x][y]]++;
dfs(x,y+1,sum+1);
X[x]--;Y[y]--;g[v[x][y]]--;
}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
cin>>c;
if(c=='1')a[i][j]=1,X[i]++,Y[j]++,g[v[i][j]]++;
}
dfs(1,1,0);
printf("%d",ans);
}
C++11(clang++ 3.9) 解法, 执行用时: 670ms, 内存消耗: 388K, 提交时间: 2020-10-20 14:50:30
#include<bits/stdc++.h>
#define Ll long long
using namespace std;
const int N=10;
int v[N][N]=
{
{0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,1,1,1,2,2,2,3,3,3},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,4,4,4,5,5,5,6,6,6},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9},
{0,7,7,7,8,8,8,9,9,9}
};
int a[N][N],X[N],Y[N],g[N];
int n,m,ans=1e9;
char c;
void dfs(int x,int y,int sum)
{
if(sum>=ans)
return;
if(y>9)
{
if(++m==1e7+5e6)
{
printf("%d",ans);
exit(0);
}
x++;
y=1;
if(X[x-1]&1)
return;
if(x==4)
if((g[1]&1)||(g[2]&1)||(g[3]&1))
return;
if(x==7)
if((g[4]&1)||(g[5]&1)||(g[6]&1))
return;
if(x==10)
{
if((g[7]&1)||(g[8]&1)||(g[9]&1))
return;
for(int i=1;i<=9;i++)
if(Y[i]&1)
return;
ans=sum;
return;
}
}
dfs(x,y+1,sum);
X[x]++;
Y[y]++;
g[v[x][y]]++;
dfs(x,y+1,sum+1);
X[x]--,Y[y]--,g[v[x][y]]--;
}
int main()
{
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
{
cin>>c;
if(c=='1')
a[i][j]=1,X[i]++,Y[j]++,g[v[i][j]]++;
}
dfs(1,1,0);
printf("%d",ans);
}