這題大概半年前有看過
前女友家教學生的題目，她是一個蠻聰明的人，印象那時候她好像不久就看出解法惹，我卻還沒甚麼想法。
阿不過這是題外話了，這題是個DFS跟我們寫數獨時的行為蠻相似的，我們會一直在往下寫，一旦發現寫錯就會回到上一格、上上格、甚至整張重寫XD。
這個行為跟DFS蠻像的，一直往下走、發現走到leaf發現不合法就回頭找其他路、直到找到正確的path。
(只是電腦比較笨，不會觀察格子之間的關係，只能簡單判斷數字田在這個格字是不是合法的)
所以一樣，就用這個概念 從(0,0)的位置從1開始猜，然後去猜(0,1)，如果發現(0,1) 1~9都不能填，那就是上一格填錯了，那就回到(0,0)然後猜2、以此類推，直到猜完(8,8)
|
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 |
bool DFS(vector<vector<char>>& board, int i, int j) { if(i == 9) //done return true; if(j == 9) return DFS(board, i+1, 0); if(board[i][j] != '.') return DFS(board, i, j+1); //guess for(char c = '1' ; c <= '9' ; c++) { //check the value is legal? int ro = i/3 , col = j/3; bool flag = false; for(int k = 0 ; k < 9 ; k++) { if(c == board[i][k] || c == board[k][j] || c == board[ro*3+k/3][col*3+k%3]) { flag = true; break; } } if(flag == true) continue; else { board[i][j] = c; if(DFS(board,i,j+1)) return true; board[i][j] = '.'; } } //all numbers are illegal, so go back last point return false; } |
這個syntax highlight theme好像好一點，但是還是找不到VSCode的theme QQ
