2 条题解
-
0梁力 (liangli) LV 8 @ 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; }
-
02024-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
- 上传者