poj 1753 2965

这两道题类似，前者翻转上下左右相邻的棋子，使得棋子同为黑或者同为白。后者翻转同行同列的所有开关，使得开关全被打开。

题意：有一4x4棋盘，上面有16枚双面棋子（一面为黑，一面为白），当翻动一只棋子时，该棋子上下左右相邻的棋子也会同时翻面。以b代表黑面，w代表白面，给出一个棋盘状态，问从该棋盘状态开始，使棋盘变成全黑或全白，至少需要翻转多少步

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int mp[5][5];

int step,flag;

int range()//遍历整个棋盘是否“清一色”

{

    for(int i=0;i<4;i++)

        for(int j=0;j<4;j++)

            if(mp[i][j]!=mp[0][0])

                return 0;

    return 1;

}

void turn(int i,int j)//翻转（i,j）棋子，以及（i,j）周围的棋子

{

    mp[i][j]=!mp[i][j];

    if(i>0) mp[i-1][j]=!mp[i-1][j];

    if(i<3) mp[i+1][j]=!mp[i+1][j];

    if(j>0) mp[i][j-1]=!mp[i][j-1];

    if(j<3) mp[i][j+1]=!mp[i][j+1];

}

int dfs(int i,int j,int k)

{

    if(k==step){

        flag = range();

        return 0;

    }

    if(flag||i==4){

        return 1;

    }

    turn(i,j);

    if(j<3) dfs(i,j+1,k+1);//一行当中的所有列

    else dfs(i+1,0,k+1);//下一行

    turn(i,j);//回溯，翻回来

     if(j<3) dfs(i,j+1,k);//下一个棋子继续dfs

    else dfs(i+1,0,k);

    return 0;

}

int main()

{

    char str[5][5];

    for(int i=0;i<4;i++)

        cin>>str[i];

    for(int i=0;i<4;i++)

        for(int j=0;j<4;j++)

            if(str[i][j]=='b') mp[i][j]=1;

            else mp[i][j]=0;

    for(step=0;step<=16;step++)

    {

        flag = 0;

        dfs(0,0,0);//（x,y）,step

        if(flag) break;

    }

    if(flag) printf("%d\n",step);

    else printf("Impossible\n");

    return 0;

}

poj 2965

一个冰箱上有4*4共16个开关，改变任意一个开关的状态（即开变成关，关变成开）时，此开关的同一行、同一列所有的开关都会自动改变状态。要想打开冰箱，要所有开关全部打开才行。

输入：一个4×4的矩阵，+表示关闭，-表示打开；

输出：使冰箱打开所需要执行的最少操作次数，以及所操作的开关坐标。

#include <iostream>

#include <cstdio>

#include  <cstring>

using namespace std;

const int Max = 0x3f3f3f3f;

int mp[5][5];

char str[5][5];

int tx[20],ty[20],ansX[20],ansY[20],ans;

int range()//判断是否“清一色”

{

    for(int i=0;i<4;i++)

        for(int j=0;j<4;j++)

            if(mp[i][j]==1)

                return 0;

    return 1;

}

void turn(int x,int y)//翻转同（i,j）同行同列的开关

{

    for(int i=0;i<4;i++)

    {

        mp[x][i]=!mp[x][i];

        mp[i][y]=!mp[i][y];

    }

    mp[x][y]=!mp[x][y];

}

void dfs(int x,int y,int step)

{

    int check = range();

    if(check==1){   //开关全打开（为0）

        if(step<ans){

                ans = step;

            for(int i=0;i<step;i++){

                ansX[i]=tx[i];

                ansY[i]=ty[i];

            }

        }

        return;

    }

    if(x>3||step>16) return;

    turn(x,y);

    tx[step]=x; ty[step]=y;

    if(y<3)  dfs(x,y+1,step+1);

    else    dfs(x+1,0,step+1);

    turn(x,y);//回溯，翻回来

    if(y<3)     dfs(x,y+1,step);

    else    dfs(x+1,0,step);

    return ;

}

int main()

{

    for(int i=0;i<4;i++)

        cin>>str[i];

    for(int i=0;i<4;i++)

        for(int j=0;j<4;j++)

            if(str[i][j]=='+') mp[i][j]=1;

            else mp[i][j]=0;

     ans = Max;

    dfs(0,0,0);//(x,y),step

    cout<<ans<<endl;

    for(int i=0;i<ans;i++)

        printf("%d %d\n",ansX[i]+1,ansY[i]+1);

    return 0;

}

递归的题总是要把人绕进去，特别是回溯那个地方。第二题还可以用其他的解法，解法很多，代码简单，但是数学不过关，看不懂，下次再看看。

巴特西

poj 1753 2965

最新文章

热门文章