poj1753Flip Game

背景：說實話，看到這道題的時候一點也不會，然後朋友說了用dfs做，雖然曾經學長講過dfs，但我沒有認真聽，是以還是一點也沒懂，然後百度了dfs，還是暈暈的，最後實在沒辦法，就看了朋友的代碼，這下才弄懂了什麼是dfs，我下面的代碼就是看了朋友的代碼後，憑借記憶，用他的思路寫出來的。

思路：對于每個格子，他要麼被反轉0次，要麼1次，由于隻有16個格子，是以他的總的情況有

是以采用dfs深度搜尋，在時間上是不成問題的。

學習：dfs算法：深度優先搜尋所遵循的搜尋政策是盡可能“深”地搜尋圖。在深度優先搜尋中，對于最新發現的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續漢下去。當結點v的所有邊都己被探尋過，搜尋将回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點并重複以上過程，整個程序反複進行直到所有結點都被發現為止。

#include <stdio.h>
int q[5][5],ok=0;
int iswin(void)
{
    int k=q[0][0];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(k!=q[i][j]) return 0;
    return 1;
}
void change(int i,int j)
{
    q[i][j]=!q[i][j];
    if(i-1>=0)   q[i-1][j]=!q[i-1][j];
    if(j-1>=0)   q[i][j-1]=!q[i][j-1];
    if(i+1<=3)   q[i+1][j]=!q[i+1][j];
    if(j+1<=3)   q[i][j+1]=!q[i][j+1];
}
void dfs(int m,int sum,int a,int b)
{
    if(ok) return;
    if(m==sum)
    {
        if(iswin()) {ok=1;printf("%d\n",sum);}
        else return;
    }
    else
    {
        for(int i=a;i<4;i++)
        {
            for(int j=b;j<4;j++)
            {
                change(i,j);
                if(j<3)  dfs(m+1,sum,i,j+1);
                if(j==3) dfs(m+1,sum,i+1,0);
                change(i,j);
            }
        }
        return;
    }
}
int main(void)
{
    char ch;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            scanf("%c",&ch);
            if(j==3) getchar();
            q[i][j]=(ch=='b')?1:0;
        }
    if(iswin()) {printf("%d\n",0);return 0;}
    for(int k=1;k<=16;k++)
        dfs(0,k,0,0);
    if(!ok) printf("Impossible\n");
    return 0;
}