首页 > 代码库 > POJ_1166_暴搜
POJ_1166_暴搜
题目描述：
有3*3的9个时钟，每个始终有0，1，2，3四种可以循环的状态码，每组数据给我们9个时钟的一种状态码。另外还有9种操作，分别使指定位置的时钟状态码加一，求使得9个时钟状态码全部置于0的最少操作数。
思路:
可以得知，每种操作数若执行了四次，则等同于不操作，所以每种操作数的次数在0-3之间，另外，题目明确告诉我们，每种状态只有一种答案。4^9,数据规模不大，把9种操作对应的位置存入一个数组，直接爆搜，也不用考虑什么情况。
后来想了一下，这题应该可以用高斯消元做，效率可以提高很多。
最后的输出格式多了一个空格，要处理的话比较麻烦，提交竟然AC了。
#include<cstdio>#include<iostream>using namespace std;int move[10][10] = {{},{0,1,1,0,1,1,},{0,1,1,1,},{0,0,1,1,0,1,1},{0,1,0,0,1,0,0,1,},{0,0,1,0,1,1,1,0,1,}, {0,0,0,1,0,0,1,0,0,1},{0,0,0,0,1,1,0,1,1,},{0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,1,1,0,1,1}};int main(){ int a[10]; for(int i = 1;i <= 9;i++) cin >> a[i]; int i1,i2,i3,i4,i5,i6,i7,i8,i9; for(i1 = 0;i1 <= 3;i1++) for(i2 = 0;i2 <= 3;i2++) for(i3 = 0;i3 <= 3;i3++) for(i4 = 0;i4 <= 3;i4++) for(i5 = 0;i5 <= 3;i5++) for(i6 = 0;i6 <= 3;i6++) for(i7 = 0;i7 <= 3;i7++) for(i8 = 0;i8 <= 3;i8++) for(i9 = 0;i9 <= 3;i9++) { int flag = 0; for(int j = 1;j <= 9;j++) { int sum = a[j]; sum += i1*move[1][j]+i2*move[2][j]+i3*move[3][j] +i4*move[4][j]+i5*move[5][j]+i6*move[6][j] +i7*move[7][j]+i8*move[8][j]+i9*move[9][j]; if(sum%4) { flag = 1; break; } } if(flag) continue; while(i1--) cout << "1 "; while(i2--) cout << "2 "; while(i3--) cout << "3 "; while(i4--) cout << "4 "; while(i5--) cout << "5 "; while(i6--) cout << "6 "; while(i7--) cout << "7 "; while(i8--) cout << "8 "; while(i9--) cout << "9 "; cout << endl; return 0; }}
POJ_1166_暴搜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。