poj 2965解題報告

5196 ワード

要旨:この問題は碁盤をひっくり返す問題とほぼ同じで、注意の違いは出力経路が必要であるため、DFSはプログラミングを便利にする.BFSを使用すると、各パスで行った決定を記録するのは難しいことに注意してください.
#include "iostream"
#include "string.h"
using namespace std;
int minroute[16],board[16];
int Minstep = 17;
bool success()
{
    for(int i = 0;i<=15;i++)
    {
        if(board[i]!=1)//         1(open)
            return false;
    }
    return true;
}
void flip(int index)
{
    int i,j;
    board[index] = !board[index];
    i= index/4, j = 0;
    while(j<=3)
    {
        board[i*4+j] = !board[i*4+j];
        j++;
    }
    j = index-4*i, i = 0;
    while(i<=3)
    {
        board[i*4+j] = !board[i*4+j];
        i++;
    }
}
void Find(int index,int step,int route[16])//top         
{
    if(success())
    {
        if(step < Minstep)
        {
            memcpy(minroute,route,sizeof(int)*step);
            minroute[step] = -1;
            Minstep = step;
        }
        return;
    }
    if(  index==16)
    {
        return;
    }
    flip(index);
    route[step] = index;
    Find(index+1,step+1,route);//    
    flip(index);
    Find(index+1,step,route);//     
}
int main()
{
    char c;
    for(int i = 0;i<=3;i++)
    {
        for(int j =0;j<=3;j++)
        {
            cin >> c;
            if(c == '+')
                board[i*4+j] = 0;
            else
                board[i*4+j] = 1;// 
        }
    }

    int route[16];
    int row,col;
    Find(0,0,route);
    cout<<Minstep<<endl;
    for(int index = 0;minroute[index]!=-1;index++)
    {
        row = (minroute[index])/4;
        col = minroute[index] -row*4;
        cout<<row+1<<' '<<col+1<<endl;
    }
    return 0;
}