注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex37 Sudoku Solver  

2015-05-26 22:45:31|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

ex37 Sudoku Solver - HT - HT·生活

A sudoku puzzle...

ex37 Sudoku Solver - HT - HT·生活

...and its solution numbers marked in red.

暴力搜索得到九宫格的解,其实应该没什么难度,和前面的深度搜索几乎一样。就是在写的时候忘了搜索到result的时候把结果保存起来,导致出来的时候答案又被覆盖了。见dfs代码

/*
*空白的部分用那个‘.’填补的
*规则:
* 1. 每一列1-9每个出现的次数不能超过1次
* 2. 每一行1-9每个出现的次数不能超过1次
* 3. 每一个3*3的格子1-9每个出现的次数不能超过1次
*暴力搜索,就是深度遍历,需要注意的就是最后退出的时候一定要把结果保存要起来
*/
class Solution {
public:
char sep = '.';
vector<vector<char>>result;
void solveSudoku(vector<vector<char>>& board) {
int startX = 0;
int startY = 0;
traverse(board,startX,startY);
board = result;
}
void traverse(vector<vector<char>>& board,int x,int y)
{
int n = board.size();
if (board[x][y] == sep)
{
for (int k = 0; k < n; k++)
{
if (isValidSudoku(board, x, y, k+1))
{
board[x][y] = k + '1';
if ((y+1) < n)
{
traverse(board, x, y+1);
board[x][y] = sep;
}
else
{

if (x == (n - 1) && y == (n - 1))
{
//一定要记录一下结果,否则就坑爹了
result = board;
return;
}
else
{
int tmp = 0;
traverse(board, x + 1, tmp);
board[x][y] = sep;
}

}

}
}
}
else
{
if ((y + 1) < n)
{
traverse(board, x, y + 1);
}
else
{
if (x == (n - 1) && y == (n - 1))
{
//一定要记录一下结果,否则就坑爹了
result = board;
return;
}
else
{
int tmp = 0;
traverse(board, x + 1, tmp);
}

}
}

}
bool isValidSudoku(vector<vector<char>>board,int x,int y,int label)
{
int m = board.size();
int n = board[0].size();
int i, j;

vector<int>mem(10, 0);
vector<int>hashDock(10, 0);
int value = 0;

//验证第x行
hashDock = mem;
hashDock[label]++;
for (i = 0; i < n; i++)
{
if (board[x][i] != sep)
{
value = board[x][i] - '0';
hashDock[value]++;
if (hashDock[value] >= 2)
return false;
}
}
//验证列
hashDock = mem;
hashDock[label]++;
for (i = 0; i < m; i++)
{
if (board[i][y] != sep)
{
value = board[i][y] - '0';
hashDock[value]++;
if (hashDock[value] >= 2)
return false;
}
}

//验证其所在的小框
hashDock = mem;
hashDock[label]++;
int num = 3;
int numX = x / 3;
int numY = y / 3;
int startX = numX * 3;
int startY = numY * 3;
for (i = 0; i < num; i++)
{
for (j = 0; j < num; j++)
{
if (board[i + startX][j + startY] != sep)
{
value = board[i + startX][j + startY] - '0';
hashDock[value]++;
if (hashDock[value] >= 2)
return false;
}
}
}
return true;
}
};

判定的时候不用像这个问题I的解一样,所有的元素都判定一遍,只需要判定加入的行和列,以及小方格没有违反规则就行了。
  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017