DFS+枚举

例题一

poj 1753 Flip Game

题目的大概意思是每一次翻动一个格子，他周围的也会跟着进行翻动，看翻动几次可以使所有的格子都变成一种颜色。

4*4的一共16个格子，如果16个格子都被翻转了还是没有达到要求则不可能达成

用DFS深搜来枚举，每次翻动一个格子判断一次是否达成，若满足未达成并且翻转次数没有达到本次要求翻转次数则继续否则就回到上一步翻转另外的格子

核心代码：

findTime(int i,int j,int deep)
{
     if(deep==step)
        if(isFinished) flag=1
     return;

     if(flag||i==5)
     return

    fan(i,j)
    if(j<5) findTime(i,j+1,deep+1)
    else  findTime(i+1,1,deep+1)
    fan(i,j)
    if(j<5) findTime(i,j+1,deep)
    else  findTime(i+1,1,deep)
    return;    
}






for(step=0;step<=16;step++)
{
     findTime(1,1,0);
     if(flag) break;
}

总体代码：

#include <iostream>
#include <cstdio>

using namespace std;

char a[5][5];
bool is[5][5]={false};
int times=0;
int step;
bool flag;

bool isfinished()
{
    char x=a[1][1];
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            if(x!=a[i][j])
                return false;
        }
    }
    return true;
}

char change(int i,int j)
{
    if(a[i][j]=='b') return 'w';
    if(a[i][j]=='w') return 'b';
}


char fan(int i,int j)
{
     a[i][j]=change(i,j);
     if(i-1>=1) a[i-1][j]=change(i-1,j);
     if(j-1>=1) a[i][j-1]=change(i,j-1);
     if(i+1<=4) a[i+1][j]=change(i+1,j);
     if(j+1<=4) a[i][j+1]=change(i,j+1);
}
void findTimes(int i,int j,int deep)
{
    if(step==deep)
    {
        flag=isfinished();
        printf("%d %d %d
",step,deep,flag);
        return;
    }
    if(flag||i==5)
        return;

    fan(i,j);
    if(j<4)
        findTimes(i,j+1,deep+1);
    else
        findTimes(i+1,1,deep+1);
    fan(i,j);
    if(j<4)
        findTimes(i,j+1,deep);
    else
        findTimes(i+1,1,deep);
    return;

}

int main()
{
    freopen("a.txt","rw",stdin);
    char temp;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            cin>>a[i][j];
        }
    }
    for(step=0;step<=16;step++)
    {
        findTimes(1,1,0);
        if(flag)break;
    }
    if(flag==true) printf("%d",step);
    else printf("Impossible");

    return 0;
}

 例题二

poj2965

 

同例题一类似，唯一不同的是需要保存每一次的状态并输出

 

刚开始用栈保存状态，结果输出是反的，用数组或者队列的话删除尾部元素又有些麻烦

想来想去看了别人的代码才发现可以直接用数组保存....不过不用删除..直接更新尾部元素就行了..简直蠢了..

 

核心dfs代码：

void dfs(int i,int j,int deep)
{
    if(deep==step)
    {
        flag=isopened();
        return;
    }
    if(flag||i==5)
    {
        return;
    }
    change(i,j);
    pos p;
    p.i=i;
    p.j=j;
    re[deep]=p;
    if(j<4) dfs(i,j+1,deep+1);
    else dfs(i+1,1,deep+1);
    change(i,j);
    if(j<4) dfs(i,j+1,deep);
    else dfs(i+1,1,deep);
    return;
}

全部代码：

#include <iostream>
#include <stack>
#include <cstdio>


using namespace std;

struct pos{
    int i;
    int j;
}Pos;


char fri1[5][5];
bool fri[5][5];
int step=0;
bool flag=0;
pos re[16];

bool isopened()
{
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
            if(fri[i][j]==0)
                return false;
    }
    return true;
}

void change(int x,int y)
{
    int i;
    fri[x][y] = !fri[x][y];
    for (i = 1; i <= 4; ++i)
    {
        fri[x][i] = !fri[x][i];
        fri[i][y] = !fri[i][y];
    }
}


void dfs(int i,int j,int deep)
{
    if(deep==step)
    {
        flag=isopened();
        return;
    }
    if(flag||i==5)
    {
        return;
    }
    change(i,j);
    pos p;
    p.i=i;
    p.j=j;
    re[deep]=p;
    if(j<4) dfs(i,j+1,deep+1);
    else dfs(i+1,1,deep+1);
    change(i,j);
    if(j<4) dfs(i,j+1,deep);
    else dfs(i+1,1,deep);
    return;
}




int main()
{
    //freopen("a.txt","rw",stdin);
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
        {
             cin>>fri1[i][j];
             if(fri1[i][j]=='+') fri[i][j]=0;
             else fri[i][j]=1;
        }

    }

    for(step=0;step<=16;step++)
    {
        dfs(1,1,0);
        if(flag) break;
    }

    if(flag)
    {
        cout<<step<<endl;
        for(int i=0;i<step;i++)
        {
            cout<<re[i].i<<" "<<re[i].j<<endl;
        }
    }
    return 0;
}