2 条题解

  • 0
    @ 2024-10-22 18:28:02
    #include <iostream>
    #include <string.h>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <iomanip>
    #include <math.h>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <ctime>
    #include <cstdlib>
    
    #define LL long long
    const int N = 9 + 10;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    int n = 9, a[N][N];
    
    
    bool check(int x, int y, int num)
    {
    	for(int i = 1; i <= n; i++)
            if(a[x][i] == num)
                return 0;
        for (int i = 1; i <= n; i++)
            if (a[i][y] == num)
    			return 0;
        int startRow = ((x - 1) / 3) * 3 + 1;
        int startCol = ((y - 1) / 3) * 3 + 1;
        for (int i = 0; i < 3; i++)
        {
    		for (int j = 0; j < 3; j++)
    		{
                if (a[startRow + i][startCol + j] == num)return 0;
    		}
        }
    	
    	return 1;
    }
    
    
    
    void dfs(int x, int y)
    {
    	if(x == n + 1)
    	{
    		for(int i = 1; i <= n; i++)
    		{
    			for(int j = 1; j <= n; j++)
    			{
    				cout << a[i][j] << ' ';
    				if(j % 3 == 0)
    				{
    					cout << "  ";
    				}
    			}
    			cout << endl;
    			if(i % 3 == 0)
    			{
    				cout << endl;
    			}
    		}
    		exit(0);
    	}
    	int xx = x, yy = y;
    	if(y < n)yy++;
    	else
    	{
    		yy = 1;
    		xx++;
    	}
    	if(a[x][y])
    	{
    		dfs(xx, yy);
    	}
    	else
    	{
    		for(int i = 1; i <= n; i++)
    		{
    			if(check(x, y, i))
    			{
    				a[x][y] = i;
    				dfs(xx, yy);
    				a[x][y] = 0;
    			}
    		}
    	}
    }
    signed main()
    {
    	for(int i = 1; i <= n; i++)
    	{
    		for(int j = 1; j <= n; j++)
    		{
    			cin >> a[i][j];
    		}
    	}
    	dfs(1, 1);
    	return 0;
    }
    
    • 0
      @ 2024-6-15 19:41:06
      #include<cstdio>
      #include<iostream>
      #include<cstring>
      #include<cmath>
      #include<iomanip>
      #include<queue>
      #include<algorithm>
      #include<vector>
      #include<stack>
      #include<set>
      using namespace std;
      #define LL long long
      const int N=100;
      using namespace std;
      int sd[11][11];
      int flag = 0;
      bool p[11][11], l[11][11], fz[11][11];
      void _out()
      {
      	if(flag==3)
      	{
      		flag=0;
      		cout<<endl;
      	}
      	for (int i = 1; i <= 3; i++)
      	{
      		for (int j = 1; j <= 3; j++)
      			cout << sd[i][j] << " ";
      		cout<<"  ";
      		for (int j = 4; j <= 6; j++)
      			cout << sd[i][j] << " ";
      		cout<<" ";
      		for (int j = 7; j <= 9; j++)
      			cout <<" "<< sd[i][j];
      		cout << endl;
      	}
      	cout<<endl;
      	for (int i = 4; i <= 6; i++)
      	{
      		for (int j = 1; j <= 3; j++)
      			cout << sd[i][j] << " ";
      		cout<<"  ";
      		for (int j = 4; j <= 6; j++)
      			cout << sd[i][j] << " ";
      		cout<<" ";
      		for (int j = 7; j <= 9; j++)
      			cout << " "<< sd[i][j] ;
      		cout << endl;
      	}
      	for (int i = 7; i <= 9; i++)
      	{
      		cout<<endl;
      		for (int j = 1; j <= 3; j++)
      			cout << sd[i][j] << " ";
      		cout<<"  ";
      		for (int j = 4; j <= 6; j++)
      			cout << sd[i][j] << " ";
      		cout<<" ";
      		for (int j = 7; j <= 9; j++)
      			cout << " "<< sd[i][j] ;
      	}
      	flag++;
      	exit(0);
      }
      void dfs(int x, int y)
      {
      	if (sd[x][y] != 0)
      		if (x == 9 && y == 9)_out();
      		else if (y == 9)dfs(x + 1, 1);
      		else dfs(x, y + 1);
      	else
      		for (int i = 1; i <= 9; i++)
      			if ((!p[x][i]) && (!l[y][i]) && (!fz[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i]))
      
      			{
      				sd[x][y] = i;
      				p[x][i] = l[y][i] = fz[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] = true;
      				if (x == 9 && y == 9)_out();
      				else if (y == 9)dfs(x + 1, 1);
      				else dfs(x, y + 1);
      				sd[x][y] = 0;
      				p[x][i] = l[y][i] = fz[(x - 1) / 3 * 3 + (y - 1) / 3 + 1][i] = false;
      			}
      }
      int main()
      {
      	for (int i = 1; i <= 9; i++)
      		for (int j = 1; j <= 9; j++)
      		{
      			int t;
      			cin >> t;
      			if (t != 0)
      				p[i][t] = l[j][t] = fz[(i - 1) / 3 * 3 + (j - 1) / 3 + 1][t] = true;
      
      			sd[i][j] = t;
      		}
      	dfs(1, 1);
      	return 0;
      }
      
      • 1

      信息

      ID
      1711
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      80
      已通过
      13
      上传者