2 条题解

  • 0
    @ 2025-10-8 16:55:23

    超时60分代码

    #include <bits/stdc++.h>
using namespace std;
int a[10][10], b[10][10];
bool vrow[10][10], vcol[10][10], vb[10][10], bk;

void dfs(int x, int y) {
    if (bk) return;
    if (x == 10) { bk = 1; return; }
    if (y == 10) { dfs(x + 1, 1); return; }

    if (a[x][y] != 0) dfs(x, y + 1);
    else {
        for (int t = 1; t <= 9; t++) {
            if (!vrow[x][t] && !vcol[y][t] && !vb[b[x][y]][t]) {
                vrow[x][t] = vcol[y][t] = vb[b[x][y]][t] = 1;
                a[x][y] = t;
                dfs(x, y + 1);
                if (bk) return;
                vrow[x][t] = vcol[y][t] = vb[b[x][y]][t] = 0;
                a[x][y] = 0;
            }
        }
    }
}

int main() {
    for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) b[i][j] = (i - 1) / 3 * 3 + (j + 2) / 3;
    char s[90];
    while (scanf("%s", s) != EOF) {
        memset(vrow, 0, sizeof(vrow)); memset(vcol, 0, sizeof(vcol)); memset(vb, 0, sizeof(vb));
        for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) {
            a[i][j] = s[(i - 1) * 9 + j - 1] - 48;
            if (a[i][j] != 0) {
                vrow[i][a[i][j]] = 1;
                vcol[j][a[i][j]] = 1;
                vb[b[i][j]][a[i][j]] = 1;
            }
        }
        bk = 0;
        dfs(1, 1);
        for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) printf("%d", a[i][j]);
        printf("\n");
    }
    return 0;
}

    超时80分代码

    #include <bits/stdc++.h>
using namespace std;
int a[10][10], b[10][10];
int vrow[10], vcol[10], vb[10];
bool bk;
map<int, int> Map;

void dfs(int x, int y) {
    if (bk) return;
    if (x == 10) { bk = 1; return; }
    if (y == 10) { dfs(x + 1, 1); return; }

    if (a[x][y] != 0) dfs(x, y + 1);
    else {
        for (int v = vrow[x] & vcol[y] & vb[b[x][y]]; v; v -= v & -v) {
            int t = Map[v & -v];
            a[x][y] = t;
            vrow[x] ^= 1 << (t - 1);
            vcol[y] ^= 1 << (t - 1);
            vb[b[x][y]] ^= 1 << (t - 1);
            dfs(x, y + 1);
            if (bk == 1) return;
            a[x][y] = 0;
            vrow[x] ^= 1 << (t - 1);
            vcol[y] ^= 1 << (t - 1);
            vb[b[x][y]] ^= 1 << (t - 1);
        }
    }
}

int main() {
    for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) b[i][j] = (i - 1) / 3 * 3 + (j + 2) / 3;
    for (int i = 1; i <= 9; i++) Map[1 << (i - 1)] = i;
    char s[90];
    while (scanf("%s", s) != EOF) {
        for (int i = 1; i <= 9; i++) vrow[i] = vcol[i] = vb[i] = (1 << 9) - 1;
        for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) {
            a[i][j] = s[(i - 1) * 9 + j - 1] - 48;
            if (a[i][j] != 0) {
                vrow[i] ^= 1 << (a[i][j] - 1);
                vcol[j] ^= 1 << (a[i][j] - 1);
                vb[b[i][j]] ^= 1 << (a[i][j] - 1);
            }
        }
        bk = 0;
        dfs(1, 1);
        for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) printf("%d", a[i][j]);
        printf("\n");
    }
    return 0;
}

    位运算（优化版）

    #include <bits/stdc++.h>
using namespace std;
int a[10][10], b[10][10], vrow[10], vcol[10], vb[10], ones[513], Map[513];
bool bk;

void dfs(int tot) {
    if (bk) return;
    if (tot == 0) { bk = true; return; }
    int tmp = 10, x, y;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++) if (a[i][j] == 0) {
            int v = vrow[i] & vcol[j] & vb[b[i][j]];
            if (v == 0) return;
            if (ones[v] < tmp) {
                tmp = ones[v];
                x = i, y = j;
            }
        }

    for (int v = vrow[x] & vcol[y] & vb[b[x][y]]; v; v -= v & -v) {
        int t = Map[v & -v];
        a[x][y] = t;
        vrow[x] ^= 1 << (t - 1);
        vcol[y] ^= 1 << (t - 1);
        vb[b[x][y]] ^= 1 << (t - 1);
        dfs(tot - 1);
        if (bk) return;
        a[x][y] = 0;
        vrow[x] ^= 1 << (t - 1);
        vcol[y] ^= 1 << (t - 1);
        vb[b[x][y]] ^= 1 << (t - 1);
    }
}

int main() {
    for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) b[i][j] = (i - 1) / 3 * 3 + (j + 2) / 3;
    memset(ones, 0, sizeof(ones));
    for (int i = 0; i < (1 << 9); i++) for (int j = i; j; j -= j & -j) ones[i]++;
    for (int i = 1; i <= 9; i++) Map[1 << (i - 1)] = i;

    char s[100];
    while (scanf("%s", s) != EOF) {
        for (int i = 1; i <= 9; i++) vrow[i] = vcol[i] = vb[i] = (1 << 9) - 1;
        int tot = 0;
        for (int i = 1; i <= 9; i++)
            for (int j = 1; j <= 9; j++) {
                a[i][j] = s[(i - 1) * 9 + j - 1] - '0';
                if (a[i][j] != 0) {
                    vrow[i] ^= 1 << (a[i][j] - 1);
                    vcol[j] ^= 1 << (a[i][j] - 1);
                    vb[b[i][j]] ^= 1 << (a[i][j] - 1);
                } else tot++;
            }
        bk = false; dfs(tot);
        for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) printf("%d", a[i][j]);
        printf("\n");
    }
    return 0;
}
    • 0
      @ 2025-10-8 16:55:09

      超时60分代码：

      #include<bits/stdc++.h>
using namespace std;
int a[10][10],b[10][10];
bool vrow[10][10],vcol[10][10],vb[10][10],bk;
void dfs(int x,int y)
{
    if(bk) return ;
    if(x==10) { bk=1;       return ; }
    if(y==10) { dfs(x+1,1); return ; }
    
    if(a[x][y]!=0) dfs(x,y+1); 
    else
    {
        for(int t=1;t<=9;t++)
        {
            if( vrow[x][t]==0 && vcol[y][t]==0 && vb[ b[x][y] ][t]==0)
            {
                vrow[x][t]=vcol[y][t]=vb[ b[x][y] ][t]=1;
                a[x][y]=t;
                dfs(x,y+1);if(bk) return;
                vrow[x][t]=vcol[y][t]=vb[ b[x][y] ][t]=0;
                a[x][y]=0;
            }
        }
    }
}
int main()
{
    for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)b[i][j]=(i-1)/3 * 3+ (j+2)/3;
    char s[90];
    while(scanf("%s",s)!=EOF)
    {
        memset(vrow,0,sizeof(vrow));memset(vcol,0,sizeof(vcol));memset(vb,0,sizeof(vb));
        for(int i=1;i<=9;i++) for(int j=1;j<=9;j++)
        {
            a[i][j]=s[(i-1)*9+j-1]-48;
            if(a[i][j]!=0)
            {
                vrow[i][a[i][j]]=1;
                vcol[j][a[i][j]]=1;
                vb[b[i][j]][a[i][j]]=1;
            }
        }
        bk=0;
        dfs(1,1);
        for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) printf("%d",a[i][j]); printf("\n");
    }
    return 0;
}

      超时80分代码： 
      #include<bits/stdc++.h>
using namespace std;
int a[10][10],b[10][10];
int vrow[10],vcol[10],vb[10];
bool bk;
map<int,int>Map;
void dfs(int x,int y)
{
    if(bk) return ;
    if(x==10) { bk=1;       return ; }
    if(y==10) { dfs(x+1,1); return ; }

      if(a[x][y]!=0) dfs(x,y+1); 
else
{
    for(int v=vrow[x] &amp; vcol[y] &amp; vb[b[x][y]]; v; v-=v&amp;-v)//v &amp; -v为lowbit(v) 
	{
        int t=Map[(v&amp;-v)]; //最小的选择 
		a[x][y]=t;
        vrow[x]     ^= 1 &lt;&lt; (t-1); 
        vcol[y]     ^= 1 &lt;&lt; (t-1);
        vb[b[x][y]] ^= 1 &lt;&lt; (t-1);
		dfs(x,y+1);if(bk==1) return ; //成功 
        a[x][y]=0;
        vrow[x]     ^= 1 &lt;&lt; (t-1); 
        vcol[y]     ^= 1 &lt;&lt; (t-1);
        vb[b[x][y]] ^= 1 &lt;&lt; (t-1);
    }
}

      

      }
int main()
{
for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)b[i][j]=(i-1)/3 * 3+ (j+2)/3;
for (int i=1;i<=9; i++)Map[1 << (i-1)] = i;
char s[90];
while(scanf("%s",s)!=EOF)
{
for(int i=1;i<=9;i++)vrow[i]=vcol[i]=vb[i]=(1<<9)-1;
for(int i=1;i<=9;i++) for(int j=1;j<=9;j++)
{
a[i][j]=s[(i-1)*9+j-1]-48;
if(a[i][j]!=0)
{
vrow[i]     ^= 1 << (a[i][j]-1);
vcol[j]     ^= 1 << (a[i][j]-1);
vb[b[i][j]] ^= 1 << (a[i][j]-1);
}
}
bk=0;
dfs(1,1);
for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) printf("%d",a[i][j]); printf("\n");
}
return 0;
}

      位运算：</p> 
      #include<bits/stdc++.h>//scy的教学代码
using namespace std;
int a[10][10],b[10][10], vrow[10], vcol[10], vb[10] , ones[513], Map[513];
//a就是最后的答案
//vrow[i]表示第i行 能填所有的数字的状态
//vcol[j]表示第j列 能填所有的数字的状态
//vb[k] 表示第k个3*3的矩阵 能填所有的数字的状态
//ones[v]表示状态v的二进制有多少个1 
//Map[x]：x只能是2^(k-1)(1<=k<=9),Map[x]表示k。
//Map[1]=1,Map[10]=2,Map[100]=3……Map[1 0000 0000]=9 

bool bk;
void dfs(int tot) 
{
	if(bk==1) return ;
    if(tot==0) {bk=True;return ;}
    int tmp=10, x, y;
    for(int i=1;i<=9;i++)
        for(int j=1; j<=9;j++)if(a[i][j]==0)
		{
            int v=vrow[i] & vcol[j] & vb[b[i][j]];//此时的v为格子(i,j)能填所有数字的状态 
            if(v==0) return ;
            if(ones[v] < tmp)//找到格子(x,y)：为目前能填最少数字的格子 
			{
                tmp = ones[v];
                x = i, y = j;
            }
        }
    
    for(int v=vrow[x] & vcol[y] & vb[b[x][y]]; v; v-=v&-v)//v & -v为lowbit(v) 
	{
        int t=Map[(v&-v)]; //最小的选择 
		a[x][y]=t;
        vrow[x]     ^= 1 << (t-1); 
        vcol[y]     ^= 1 << (t-1);
        vb[b[x][y]] ^= 1 << (t-1);
		dfs(tot-1);if(bk==1) return ; //成功 
        a[x][y]=0;
        vrow[x]     ^= 1 << (t-1); 
        vcol[y]     ^= 1 << (t-1);
        vb[b[x][y]] ^= 1 << (t-1);
    }
}
int main() 
{
    ////格子(x,y)所在的3*3的矩阵的编号，编号为1~9 
    for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)b[i][j]=(i-1)/3 * 3+ (j+2)/3;
    memset(ones,0,sizeof(ones));
	for(int i=0;i< 1<<9; i++) for(int j=i;j;j -= j&-j) ones[i]++;
    for (int i=1;i<=9; i++)Map[1 << (i-1)] = i;
	
    char s[100];
    while (scanf("%s", s)!=EOF) 
	{
		for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)a[i][j]=s[(i-1)* 9+j -1]-'0';//转换
        
        for(int i=1;i<=9;i++)vrow[i]=vcol[i]=vb[i]=(1<<9)-1;
        
        int tot=0;//tot统计有多少个a[i][j]==0 
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
                if(a[i][j]!=0)
                {
                    vrow[i]     ^= 1 << (a[i][j]-1); 
                    vcol[j]     ^= 1 << (a[i][j]-1);
                    vb[b[i][j]] ^= 1 << (a[i][j]-1);
                } 
                else tot++;
                
        bk=False;dfs(tot);
        
        for(int i=1;i<=9;i++)for(int j=1;j<=9;j++) printf("%d",a[i][j]);
        printf("\n");
    }
    return 0; 
}

      用堆优化反而超时，要10秒，不知为什么，这里也贴下堆优化超时的代码： 
      #include<bits/stdc++.h>//scy的教学代码
using namespace std;
int a[10][10],b[10][10], vrow[10], vcol[10], vb[10] , ones[513], Map[513];
//a就是最后的答案
//vrow[i]表示第i行 能填所有的数字的状态
//vcol[j]表示第j列 能填所有的数字的状态
//vb[k] 表示第k个3*3的矩阵 能填所有的数字的状态
//ones[v]表示状态v的二进制有多少个1 
//Map[x]：x只能是2^(k-1)(1<=k<=9),Map[x]表示k。
//Map[1]=1,Map[10]=2,Map[100]=3……Map[1 0000 0000]=9 
struct node{
    int k,x,y;
    bool operator < (const node &a) const {return k>a.k;}
};
priority_queue<node> q;
bool bk;
void dfs(int tot) 
{
	if(bk==1) return ;
    if(tot==0) {
        bk=True;
        return ;
    }

      int k = q.top().k ,x = q.top().x, y = q.top().y;q.pop();

for(int v=vrow[x] &amp; vcol[y] &amp; vb[b[x][y]]; v; v-=v&amp;-v)//v &amp; -v为lowbit(v) 
{
    int t=Map[(v&amp;-v)]; //最小的选择 
	a[x][y]=t;
    vrow[x]     ^= 1 &lt;&lt; (t-1); 
    vcol[y]     ^= 1 &lt;&lt; (t-1);
    vb[b[x][y]] ^= 1 &lt;&lt; (t-1);
    
	dfs(tot-1);if(bk==1) return ; //成功 
    
    a[x][y]=0;
    vrow[x]     ^= 1 &lt;&lt; (t-1); 
    vcol[y]     ^= 1 &lt;&lt; (t-1);
    vb[b[x][y]] ^= 1 &lt;&lt; (t-1);
}
q.push({k,x,y});

      

      }
int main()
{
////格子(x,y)所在的3*3的矩阵的编号，编号为1~9
for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)b[i][j]=(i-1)/3 * 3+ (j+2)/3;
memset(ones,0,sizeof(ones));
for(int i=0;i< 1<<9; i++) for(int j=i;j;j -= j&-j) ones[i]++;
for (int i=1;i<=9; i++)Map[1 << (i-1)] = i;
      

      char s[100];
while (scanf("%s", s)!=EOF) 
{
    while(!q.empty())q.pop();
	for(int i=1;i&lt;=9;i++)for(int j=1;j&lt;=9;j++)a[i][j]=s[(i-1)* 9+j -1]-'0';//转换
    
    for(int i=1;i&lt;=9;i++)vrow[i]=vcol[i]=vb[i]=(1&lt;&lt;9)-1;
    
    int tot=0;//tot统计有多少个a[i][j]==0 
    for(int i=1;i&lt;=9;i++)
        for(int j=1;j&lt;=9;j++)
            if(a[i][j]!=0)
            {
                vrow[i]     ^= 1 &lt;&lt; (a[i][j]-1); 
                vcol[j]     ^= 1 &lt;&lt; (a[i][j]-1);
                vb[b[i][j]] ^= 1 &lt;&lt; (a[i][j]-1);
            } 
            else tot++;
    for(int i=1;i&lt;=9;i++)
        for(int j=1;j&lt;=9;j++)
            if(a[i][j]==0)
            {
                int v=vrow[i] &amp;vcol[j] &amp;vb[b[i][j]];
                q.push({ones[v],i,j});
            } 
            
    bk=False;dfs(tot);
    
    for(int i=1;i&lt;=9;i++)for(int j=1;j&lt;=9;j++) printf("%d",a[i][j]);
    printf("\n");
}
return 0; 

      

      }
      </p>
      • 1

      *【位运算搜索】数独Ⅱ

      信息

      ID
      1081
      时间
      1500ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      339
      已通过
      46
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 8ms
      4. Powered by Hydro v5.0.1 Community