| 记录编号 |
43526 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
黑白棋游戏 |
最终得分 |
100 |
| 用户昵称 |
 Truth.Cirno |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.079 s |
| 提交时间 |
2012-10-11 08:58:21 |
内存使用 |
6.21 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
const short RUL[2][2]={{1,0},{0,1}};
struct
{
int /*rec,*/dad,deep;
short xx1,yy1,xx2,yy2;
bool info[5][5];
}que[70000];
bool used[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
bool tar[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
bool dupped(int pos)
{
// int i;
// for (i=0;i<pos;i++)
// if (que[i].rec==que[pos].rec)
// return(1);
if (used[que[pos].info[1][1]][que[pos].info[1][2]][que[pos].info[1][3]][que[pos].info[1][4]][que[pos].info[2][1]][que[pos].info[2][2]][que[pos].info[2][3]][que[pos].info[2][4]][que[pos].info[3][1]][que[pos].info[3][2]][que[pos].info[3][3]][que[pos].info[3][4]][que[pos].info[4][1]][que[pos].info[4][2]][que[pos].info[4][3]][que[pos].info[4][4]])
return(1);
used[que[pos].info[1][1]][que[pos].info[1][2]][que[pos].info[1][3]][que[pos].info[1][4]][que[pos].info[2][1]][que[pos].info[2][2]][que[pos].info[2][3]][que[pos].info[2][4]][que[pos].info[3][1]][que[pos].info[3][2]][que[pos].info[3][3]][que[pos].info[3][4]][que[pos].info[4][1]][que[pos].info[4][2]][que[pos].info[4][3]][que[pos].info[4][4]]=true;
return(0);
}
bool okayed(int pos)
{
if (tar[que[pos].info[1][1]][que[pos].info[1][2]][que[pos].info[1][3]][que[pos].info[1][4]][que[pos].info[2][1]][que[pos].info[2][2]][que[pos].info[2][3]][que[pos].info[2][4]][que[pos].info[3][1]][que[pos].info[3][2]][que[pos].info[3][3]][que[pos].info[3][4]][que[pos].info[4][1]][que[pos].info[4][2]][que[pos].info[4][3]][que[pos].info[4][4]])
return(1);
return(0);
}
void printans(int pos)
{
if (pos)
{
printans(que[pos].dad);
cout<<que[pos].xx1<<que[pos].yy1<<que[pos].xx2<<que[pos].yy2<<endl;
}
}
int main(void)
{
freopen("bwgame.in","r",stdin);
freopen("bwgame.out","w",stdout);
int i,j,k/*,k1,k2*/,tail=0,head=0/*,tar=0*/,x,y,temp[5][5];
for (i=1;i<=4;i++)
for (j=1;j<=4;j++)
{
scanf("%1d",&que[0].info[i][j]);
// que[0].rec=(que[0].rec<<1)+que[0].info[i][j];
}
used[que[0].info[1][1]][que[0].info[1][2]][que[0].info[1][3]][que[0].info[1][4]][que[0].info[2][1]][que[0].info[2][2]][que[0].info[2][3]][que[0].info[2][4]][que[0].info[3][1]][que[0].info[3][2]][que[0].info[3][3]][que[0].info[3][4]][que[0].info[4][1]][que[0].info[4][2]][que[0].info[4][3]][que[0].info[4][4]]=true;
for (i=1;i<=4;i++)
for (j=1;j<=4;j++)
{
scanf("%1d",&temp[i][j]);
// tar=(tar<<1)+temp;
}
tar[temp[1][1]][temp[1][2]][temp[1][3]][temp[1][4]][temp[2][1]][temp[2][2]][temp[2][3]][temp[2][4]][temp[3][1]][temp[3][2]][temp[3][3]][temp[3][4]][temp[4][1]][temp[4][2]][temp[4][3]][temp[4][4]]=true;
while (head>=tail)
{
for (i=1;i<=4;i++)
for (j=1;j<=4;j++)
for (k=0;k<2;k++)
{
x=RUL[k][0]+i;
y=RUL[k][1]+j;
if (x>4||y>4)
continue;
if (que[tail].info[i][j]==que[tail].info[x][y])
continue;
head++;
que[head]=que[tail];
que[head].info[i][j]=que[tail].info[x][y];
que[head].info[x][y]=que[tail].info[i][j];
// que[head].rec=0;
// for (k1=1;k1<=4;k1++)
// for (k2=1;k2<=4;k2++)
// que[head].rec=(que[head].rec<<1)+que[head].info[k1][k2];
if (dupped(head))
{
head--;
continue;
}
que[head].dad=tail;
que[head].deep++;
que[head].xx1=i;
que[head].yy1=j;
que[head].xx2=x;
que[head].yy2=y;
if (okayed(head))
{
cout<<que[head].deep<<endl;
printans(head);
return(0);
}
// if (tar==que[head].rec)
// {
// cout<<que[head].deep<<endl;
// printans(head);
// return(0);
// }
}
tail++;
}
return(0);
}