POJ1753-Flip Game(枚舉)

簡單枚舉。

每個格子只有翻與不翻兩種狀態(翻兩次跟沒翻一樣)。總共16個格子，最多只能翻出2^16種狀態。

Code:

[cpp]  #include <stdio.h>  
 
bool s[20][20]; 
int best; 
 
int check() 
{ 
    int i, j, tot = 0; 
    for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j]; 
    if(tot == 0 || tot == 16) return 1; 
    return 0; 
} 
void Echange(int x, int y) 
{ 
    s[x][y] = !s[x][y]; 
    s[x+1][y] = !s[x+1][y]; 
    s[x][y+1] = !s[x][y+1]; 
    if(x>0) s[x-1][y] = !s[x-1][y]; 
    if(y>0) s[x][y-1] = !s[x][y-1]; 
 
} 
void Search(int k, int ans) 
{ 
    int x, y; 
    if(16 == k) { 
        if( check()&& ans <best) best = ans; 
    }else { 
        x = k /4; 
        y = k %4; 
        Search(k+1,ans);//不翻  
        Echange(x, y); 
        Search(k+1,ans+1);//翻  
        Echange(x, y); 
    } 
} 
void work() 
{ 
    int i, j; 
    char c; 
    for(i = 0; i<4; i++) 
    { 
        for(j = 0; j<4; j++){ 
            scanf("%c", &c); 
            if(c=='w') s[i][j] = 0; 
            else s[i][j] = 1; 
        } 
        getchar(); 
    } 
    //for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("\n");}  
    best = 1000; 
    Search(0, 0); 
    for(i=0;i<4;i++) 
    for(j=0;j<4;j++) 
       s[i][j] =!s[i][j]; 
    Search(0, 0); 
    if(best != 1000) printf("%d\n",best); 
    else printf("Impossible\n"); 
} 
 
int main() 
{ 
    work(); 
    return 0; 
} 

#include <stdio.h>

bool s[20][20];
int best;

int check()
{
    int i, j, tot = 0;
    for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j];
    if(tot == 0 || tot == 16) return 1;
    return 0;
}
void Echange(int x, int y)
{
    s[x][y] = !s[x][y];
    s[x+1][y] = !s[x+1][y];
    s[x][y+1] = !s[x][y+1];
    if(x>0) s[x-1][y] = !s[x-1][y];
    if(y>0) s[x][y-1] = !s[x][y-1];

}
void Search(int k, int ans)
{
    int x, y;
    if(16 == k) {
        if( check()&& ans <best) best = ans;
    }else {
        x = k /4;
        y = k %4;
        Search(k+1,ans);//不翻
        Echange(x, y);
        Search(k+1,ans+1);//翻
        Echange(x, y);
    }
}
void work()
{
    int i, j;
    char c;
    for(i = 0; i<4; i++)
    {
        for(j = 0; j<4; j++){
            scanf("%c", &c);
            if(c=='w') s[i][j] = 0;
            else s[i][j] = 1;
        }
        getchar();
    }
    //for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("\n");}
    best = 1000;
    Search(0, 0);
    for(i=0;i<4;i++)
    for(j=0;j<4;j++)
       s[i][j] =!s[i][j];
    Search(0, 0);
    if(best != 1000) printf("%d\n",best);
    else printf("Impossible\n");
}

int main()
{
    work();
    return 0;
}