| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么就偏偏最后一组数据过不了呢?In Reply To:为WA的同志们提供几组测试数据 Posted by:zdqpp at 2010-05-13 17:36:43 #include<iostream>
using namespace std;
bool map[4][4];
int ans=33;
int x[4][4];//存储当前解
int bestx[4][4];//存储当前最优解
void init() //初始化数组map
{
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
{
char c;
cin>>c;
if (c=='-')
map[i][j]=true;
else map[i][j]=false;
}
}
void turn (int x,int y) //翻转
{
if (x>=0&&x<=3&&y>=0&&y<=3)
map[x][y] = !map[x][y];
return;
}
void flip(int pos) //翻转
{
int i=pos/4;
int j=pos%4;
turn(i,j);
for (int k=0;k<4;k++)
{
turn(i,k);
turn(k,j);
}
}
bool finished()//判断是否完成
{
int sum=0;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
sum+=map[i][j];
if (sum%16)
return false;
else
return true;
}
void dfs(int pos,int step)
{
if (finished())
{
if (ans>step)
{
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
bestx[i][j]=x[i][j];//更新最优解
ans=step;
return;
}
}
if (pos>=16)
return;
int i=pos/4;
int j=pos%4;
x[i][j]=0;
dfs(pos+1,step);
x[i][j]=1;
flip(pos);
dfs(pos+1,step+1);
flip(pos);
x[i][j]=0;
}
int main()
{
init();
dfs(0,0);
if (ans==33)
cout<<"Impossible"<<endl;
else
{
cout<<ans<<endl;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
if(bestx[i][j]==1)
cout<<i+1<<" "<<j+1<<endl;
}
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator