营销型网站建设哪家便宜,厦门网络推广,小游戏开发,建站行业的乱象http://poj.org/problem?id2676POJ 2676 Sudoku也是求解规模为9*9的数独问题#xff0c;与POJ 3074 Sudoku相同的问题#xff0c;只是修改了输入输出格式而已。。。所以也不废话了#xff0c;嘿嘿。。。 #includestdio.h
#includestring.h
const int MAX_C… http://poj.org/problem?id2676POJ 2676 Sudoku也是求解规模为9*9的数独问题与POJ 3074 Sudoku相同的问题只是修改了输入输出格式而已。。。所以也不废话了嘿嘿。。。 #includestdio.h
#includestring.h
const int MAX_COLOUMN 819*99*99*92;//最多出现列数
const int MAX_ROW 81*92;//最多出现的列数int cnt[MAX_COLOUMN];//cnt[i]统计第i列1的个数
int most,coloumn;
bool ans[MAX_ROW];//ans存放最终选中的行
//跳舞链中的节点
struct Point
{int up,down,left,right;//上下左右int coloumn;//该点所在的列标int row;//行标
}node[MAX_ROW*MAX_COLOUMNMAX_COLOUMN];//初始化跳舞链信息为空
void init(int m)
{int i;for(i0;im;i){node[i].downi;node[i].up i;node[i].coloumni;node[i].lefti-1;node[i].righti1;cnt[i]0;}node[0].left m;node[m].right 0;
}void remove(int c)//删除c列上所有1元素所在的行
{node[node[c].right].leftnode[c].left;node[node[c].left].rightnode[c].right;int t,tt;for(tnode[c].down;t!c;tnode[t].down)//从上到下从左到右删除该列上的每一非零元素所在行信息{for(tt node[t].right;tt!t;ttnode[tt].right)//删除非零元素所在行{cnt[node[tt].coloumn]--;node[node[tt].down].up node[tt].up;node[node[tt].up].down node[tt].down;}}
}void resume(int c)//还原c列上所有1元素所在的行
{int t,tt;for(tnode[c].up;t!c;tnode[t].up)//从下往上从左到右还原该c列中1所在的行信息{for(ttnode[t].left;tt!t;ttnode[tt].left){cnt[node[tt].coloumn];node[node[tt].up].downtt;node[node[tt].down].uptt;}}node[node[c].right].leftc;node[node[c].left].rightc;
}bool dfs(int k)//k为已经选中的行的数目
{int i,j;if(kmost)return false;if(node[coloumn].right coloumn)//当前跳舞链已为空{if(kmost)most k;return true;}int t coloumn1;int c;//选取当前矩阵中1最少的列for(inode[coloumn].right;i!coloumn;inode[i].right){if(cnt[i]t){ci;tcnt[i];if(t1)break;}}remove(c);//删除列c中所有1所在的行//删除时从左到右从上到下还原时从下到上从右到左for(i node[c].down;i!c;inode[i].down){for(jnode[i].right;j!i;jnode[j].right){remove(node[j].coloumn);}ans[node[j].row]true;if(dfs(k1)){return true;}ans[node[j].row]false;for(jnode[j].left;j!i;jnode[j].left){resume(node[j].coloumn);}}resume(c);return false;
}
bool graph[MAX_ROW][MAX_COLOUMN];
void addrow(int i,int j,int k)
{int curr (i*9j)*9k;graph[curr][(i*9j)]true;graph[curr][81i*9k]true;graph[curr][8181j*9k]true;int tr i/3;int tc j/3;graph[curr][818181(tr*3tc)*9k]true;
}char str[MAX_ROW];
int main()
{int N,M,i,j,k;int T;while(scanf(%d,T)!EOF){while(T--){N81*9;M 9*99*99*99*9;coloumn M;int curcoloumn1;//当前节点编号init(coloumn);memset(graph,0,sizeof(graph));for(i0;i9;i){scanf(%s,str);for(j0;j9;j){if(str[j]0){for(k0;k9;k)//遍历每一种颜色{addrow(i,j,k);}continue;}k str[j]-1;addrow(i,j,k);}}for(i0;iN;i){int start cur;//记录第i列的开始点编号int pre cur;//记录该列中当前1的左边第一个1编号for(j0;jM;j){// scanf(%d,n);if(graph[i][j])//跳舞链中仅插入非0元素{int pos j;node[cur].up node[pos].up;node[node[pos].up].down cur;node[cur].down pos;node[pos].up cur;cnt[pos];//该列1的个数1node[cur].coloumn pos;node[cur].left pre;node[pre].right cur;node[cur].right start;node[start].leftcur;node[cur].row i;precur;}}}most N1;//记录最少需要选中的行数memset(ans,false,sizeof(ans));dfs(0);// printf(Yes, I found it\n);for(i0;i81;i){ if(i!0i%90)printf(\n);for(j0;j9;j)if(ans[i*9j]){printf(%d,j1);break;}}printf(\n);}}return 0;
}转载于:https://www.cnblogs.com/AndreMouche/archive/2011/02/24/1964147.html
