POJ 3279 Fliptile(バイナリ列挙、繰返し、POJ 1426 Find The Multiple、詳細)
33892 ワード
POJ 3279 Fliptile
テストプラットフォームFarmer John knows that an intellectually satisfied cow is a happy cow who will give more milk.He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word “IMPOSSIBLE”.
Input Line 1: Two space-separated integers: M and N Lines 2…M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white
Output Lines 1…M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
Sample Input 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
Sample Output 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
問題の難点
質問:乳牛が(x,y)のタイルをひっくり返すと同時に周囲のタイルに影響し、どのようにして最も早く最適な案(すべてのタイルが白い)を確定することができますか?
①、初歩的な考え方暴力列挙.N=15,M=15の場合,ケース数は2(15*15)であり,時間的複雑度が高すぎる.
②、思考変化の列挙+繰返し.最初の行が現れる可能性のある場合を挙げ、前の行の場合に次の行が反転する場合を提示し、最後に結果を検証します.
具体案
1、バイナリ列挙タイルごとに2つの変化がある:黒、白.この性質を用いて,バイナリ列挙を用いることができる.1行目が最も多い場合数は215時間複雑度で条件を満たす.
//
//test ：
for(int i=0; i<(1<<m); i++){
memset(test, 0, sizeof(test));
for(int j=0; j<m; j++)
test[0][m-j-1] = (i>>j)&1;
}
①、「< 1行目が反転した場合を2 m、[0,2 m-1]の区間では、それぞれの数が1行目の反転を表している.
②、">>右シフト演算と"&"x>>j:xのバイナリを右シフトjビット例えば:1010>>1=101 x&1:xのバイナリでの最低ビットを決定する.たとえば、1010&1=0101&1=1
ここで私は後から前へ列挙して、辞書の順序の最小の先列挙を保証するために注目します.
2、プッシュはまず、1行目のタイルの白黒を確定し、次の行の白黒をプッシュします.例えば(0,1)が黒いタイルである場合、(1,1)のタイルは、次の繰返し中に(1,1)を反転してこそ(0,1)のタイルの色を変えることができるため、反転しなければならない.
// (x, y)
int judge(int x, int y){
int tmp = file[x][y];
for(int i=0; i<5; i++){
int ddx = x+dx[i];
int ddy = y+dy[i];
if(ddx>=0&&ddx<n&&ddy>=0&&ddy<m)
tmp += test[ddx][ddy];
}
return tmp%2;
}
//
for(int i=1; i<n; i++)
for(int j=0; j<m; j++)
if(judge(i-1, j))
test[i][j]=1;
3、検証最後の行の反転状況をプッシュした場合、最後の行が全白であるかどうかを検証するだけです.全白であれば,現在の第1行の状況から繰り出される反転状況が解である.
//
for(int i=0; i<m; i++)
if(judge(n-1, i))
return -1;
インプリメンテーションコード
#include
");
//
else
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(j!=0)
printf(" ");
printf("%d", ans[i][j]);
}
printf("
");
}
return;
}
int main(){
while(scanf("%d%d", &n, &m)==2){
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
scanf("%d", &file[i][j]);
slove();
}
return 0;
}
バイナリ列挙拡張テーマPOJ 1426 Find The Multiple
テストプラットフォームDescription
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits. Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input. Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable. Sample Input
2 6 19 0 Sample Output
10 100100100100100100 111111111111111111
インプリメンテーションコード
#include
", m);
return;
}
}
return ;
}
int main(){
while(scanf("%d", &n)==1){
if(n==0) break;
f();
}
return 0;
}
もし文章があなたに役に立つなら、私にほめてください.