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;
}