POJ 2965 The Pilots Brothers' refrigerator
アドレス:http://poj.org/problem?id=2965
标题:この问题は反転棋の问题に似ていて、1つの4*4からなる+-ロックを解錠する最小のステップと操作の順序を求めます.ロックを変更するたびに、同じ列のロックが変更されます.
PS:主にパスを追加して保存しているので、DFSで検索するしかないので、枝切りに注意してタイムアウトを防ぐ.
标题:この问题は反転棋の问题に似ていて、1つの4*4からなる+-ロックを解錠する最小のステップと操作の順序を求めます.ロックを変更するたびに、同じ列のロックが変更されます.
PS:主にパスを追加して保存しているので、DFSで検索するしかないので、枝切りに注意してタイムアウトを防ぐ.
#include<iostream>
using namespace std;
bool map[4][4];
int flag;
int step;
int r[16];
int c[16];
bool judge()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(map[i][j]) return 0;
return 1;
}
void change(int row,int col)
{
for(int i=0;i<4;i++)
if(i!=col) map[row][i]=!map[row][i];
for(int i=0;i<4;i++)
if(i!=row) map[i][col]=!map[i][col];
map[row][col]=!map[row][col];
return ;
}
void dfs(int row,int col,int deep)
{
if(deep==step) {flag=judge();return ;}
if(row==4||flag) return ;
change(row,col);
r[deep]=row+1;
c[deep]=col+1;
if(col<3)
dfs(row,col+1,deep+1);
else
dfs(row+1,0,deep+1);
change(row,col);
if(col==3)
dfs(row+1,0,deep);
else
dfs(row,col+1,deep);
return ;
}
int main()
{
int i,j;
char temp;
flag=0;
memset(map,0,sizeof(map));
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
cin>>temp;
if(temp=='+') map[i][j]=1;
}
for(step=0;step<17;step++)
{
dfs(0,0,0);
if(flag) break;
}
cout<<step<<endl;
for(i=0;i<step;i++)
{
cout<<r[i];
cout<<" ";
cout<<c[i];
cout<<endl;
}
// system("PAUSE");
return 0;
}