【leetcode】 Sudoku Solver

地址

https://leetcode.com/problems/sudoku-solver/description/

题目

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.

思路

第一眼暴力,然后觉得不可能这么sb,还以为要用dancing-link,后来觉得做个leetcode怎么可能会需要用到这种东西。百度一发题解,果然如此,就是sb暴力

代码

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
class Solution {
public:
int ff=0,ur[10][10],ul[10][10],uu[10][10];
vector<vector<char>> mp,ans;
void init(void)
{
for(int i=0;i<9;i++)
{
for(int j=1;j<=9;j++)
ur[i][j]=ul[i][j]=uu[i][j]=1;
for(int j=0;j<9;j++)
{
if(mp[i][j]!='.')
ur[i][mp[i][j]-'0']=0;
if(mp[j][i]!='.')
ul[i][mp[j][i]-'0']=0;
}
}
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(mp[i][j]!='.')
uu[i/3*3+j/3][mp[i][j]-'0']=0;
}
void dfs(int x,int y)
{
if(ff) return;
if(x==9)
{
ff=1,ans=mp;
return;
}
if(mp[x][y]!='.')
{
dfs(x+(y==8),(y+1)%9);
return ;
}
for(int i=1;i<10;i++)
if(ur[x][i]&&ul[y][i]&&uu[x/3*3+y/3][i])
{
ur[x][i]=ul[y][i]=uu[x/3*3+y/3][i]=0;
mp[x][y]='0'+i;
dfs(x+(y==8),(y+1)%9);
mp[x][y]='.';
ur[x][i]=ul[y][i]=uu[x/3*3+y/3][i]=1;
}
}
void solveSudoku(vector<vector<char>>& board) {
mp=board;
init();
dfs(0,0);
board=ans;
}
};