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;
    }
    

    信息

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