TIOJ1235

題敘

https://tioj.ck.tp.edu.tw/problems/1235
同數獨問題不過元素改成 $R O Y G B I P L W$
問空格應填入甚麼元素

想法

記錄每行、每列、每個九宮格有哪些元素已經被使用
接著DFS每個空著的元素,枚舉是否有可能是答案

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//By Koios1143
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
char arr[9][9],new_arr[9][9],input,var[9]={'R','O','Y','G','B','I','P','L','W'};
bool used_rect[9][128];
bool used_row[9][128];
bool used_col[9][128];
vector<pii> emp;
int get_rect(int x,int y){
if(x<3){
if(y<3) return 0;
else if(y<6) return 1;
else return 2;
}
else if(x<6){
if(y<3) return 3;
else if(y<6) return 4;
else return 5;
}
else{
if(y<3) return 6;
else if(y<6) return 7;
else return 8;
}
}
bool dfs(){
if(emp.empty())
return true;
int x,y;
tie(x,y)=emp.back();
emp.pop_back();
for(int i=0 ; i<9 ; i++){
if(!used_rect[get_rect(x,y)][var[i]] && !used_row[y][var[i]] && !used_col[x][var[i]]){
new_arr[x][y]=var[i];
used_rect[get_rect(x,y)][var[i]] = used_row[y][var[i]] = used_col[x][var[i]] = true;
if(dfs()) return true;
used_rect[get_rect(x,y)][var[i]] = used_row[y][var[i]] = used_col[x][var[i]] = false;
new_arr[x][y]='*';
}
}
emp.emplace_back(x,y);
return false;
}
int main(){
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
cin>>input;
arr[i][j]=input;
if(input=='*'){
emp.emplace_back(i,j);
}
used_rect[get_rect(i,j)][input]=true;
used_row[j][input]=true;
used_col[i][input]=true;
}
}
dfs();
for(int i=0 ; i<9 ; i++){
for(int j=0 ; j<9 ; j++){
if(arr[i][j] == '*')
cout<<new_arr[i][j];
}
cout<<'\n';
}
return 0;
}

複雜度分析

輸入複雜度為 $O(n^2)$

DFS複雜度最差為 $O(9^{n^{2}})$ ,但是實際上因為有剪枝,加上空格數量問題,所以實際上會比這個小很多很多