题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9,M = 1 << N;
int ones[M],map[M];
int row[M],col[N],cell[3][3];
char str[100];
void init()
{
for(int i = 0;i<N;i++) row[i] = col[i] = (1 << N) - 1;//每一个状态都拉满
for(int i = 0;i<3;i++)
{
for(int j = 0;j<3;j++)
{
cell[i][j] = (1 << N) - 1;
}
}
}
void draw(int x,int y,int t,bool st)
{
if(st) str[x * N + y] = t + '1';
else str[x * N + y] = '.';
int v = 1 << t;
if(!st) v = -v;
row[x] -= v;
col[y] -= v;
cell[x/3][y/3] -= v;
}
int lowbit(int x)
{
return x & -x;
}
int get(int x,int y)
{
return row[x] & col[y] & cell[x/3][y/3];
}
bool dfs(int cnt)
{
if(!cnt) return true;
int minv = 10,x,y;
for(int i = 0;i<N;i++)
{
for(int j = 0;j<N;j++)
{
if(str[i*N+j]=='.')
{
int t = get(i,j);
if(ones[t] < minv)
{
x = i,y = j;
minv = ones[t];
}
}
}
}
int st = get(x,y);
for(int i = st;i;i-=lowbit(i))
{
int t = map[lowbit(i)];
draw(x,y,t,true);
if(dfs(cnt - 1)) return true;
draw(x,y,t,false);
}
return false;
}
int main()
{
for(int i = 0;i<N;i++) map[1<<i] = i;
for(int i = 0;i<1<<N;i++)
{
for(int j = 0;j<N;j++)
{
ones[i] += i >> j & 1;
}
}
while(cin >> str,str[0]!='e')
{
init();
int cnt = 0;
for(int i = 0,k = 0;i<N;i++)
{
for(int j = 0;j<N;j++,k++)
{
if(str[k]!='.')
{
int t = str[k] - '1';
draw(i,j,t,true);//造出9空格
}
else cnt++;//统计.的数量
}
}
dfs(cnt);
puts(str);
}
return 0;
}