USACO 5.2.3 Wisconsin Squares
中文题意
这题首先看到的是时限:5S.这么长的时间,我们可以暴力啦.一顿暴搜就OK了.其中注意几点:I.那个顺序,是一个一个比的,而不是先把所有的类型比较,然后row比较,最后col比较.一开始我是按后面的排序搞的,结果sample都过不去.sample的输出是E 2 1;E 2 3;D 1 4 我的输出是E 2 3;D 1 4;E 2 1.可以看出后面这组数据是把类型,row,col分开比较.但是这样是不对的.所以应该同时比较一个步骤的类型,row,col.II.如果放置的小牛不可以被移出去[因为一共16次完成移动],移动的时候周围不可以有相同类型的牛.III.最后注意看牛群数目是否一样,即3A 3B 3C 4D 3E.IV.最重要的的是.这题非常操蛋啊.数据就一组.而且就是sample.这个让我蛋疼不已啊.下面附上我的代码:[那个解可以不更新,因为每次都是按顺序找的.所以第一个解肯定是最有解]
/
ID:qcx97811
LANG:C
TASK:wissqu
/
#include
#include
#include
#include
char cow[66];//原矩阵
char goal[6]={3,3,3,4,3};//最终牛群
char now[6],num[6];//now是搜索结束时的牛群数 num是当前的牛群数
char used[66];//某个点是否已经是小牛了,也就是不可以换出去
typedef struct
{//结构体,c表示字符 n_r表示row n_c表示col
char c
char n_r,n_c
}Node
Node way[18],best[18];//best表示最有解 way是搜索的中间解
int sum//sum是总结过数
int idx
void check_best()
{//检查best 然后更新est
char s1[18],s2[18];
int i,j
int k
for(i=0i<16;i++)
{
if(best[i].c < way[i].c)
return ;
if(best[i].c == way[i].c)
{
if(best[i].n_r < way[i].n_r)
return ;
if(best[i].n_r == way[i].n_r)
{
if(best[i].n_c <= way[i].n_c)
return
break
}
else
break
}
else
{
break
}
}
for(i=0i<16;i++)
{
best[i]=way[i];
}
}
int can_place(int r,int c,char ch)
{//可以把ch放置在 [r,c]这个点上
int i,j
if(1==used[r4+c])
return 0
for(i=r-1i<r+2;i++)
{
if(i>=0&i<4)
{
for(j=c-1j<c+2;j++)
{
if(j>=0&j<4)
{
if(ch == cow[i4+j])
return 0
}
}
}
}
return 1
}
void search(int level)
{
int i,j
int r,c
char ch
if(level>16)
{//已经操作16次了
memset(now,0,sizeof(now));
for(i=0i<4;i++)
{
for(j=0j<4;j++)
{
now[cow[i4+j]-‘A’]++
}
}
for(i=0i<5;i++)
{
if(now[i] != goal[i])
break
}
if(5 != i)//牛群数目不对
return
if(0 == sum)
{
for(i=0i<16;i++)
best[i]=way[i];
}
else
{
check_best();
}
sum++
return ;
}
for(i=0i<5;i++)
{
if(num[i]>=goal[i])
continue//这种牛已经放置完成 不需要放置该种牛群
num[i]++
for(r=0r<4;r++)
{
for(c=0c<4;c++)
{
if(can_place(r,c,i+‘A’))
{
ch=cow[r4+c];
cow[r4+c]=i+‘A’
used[r4+c]=1
idx++
way[level-1].c=i+‘A’
way[level-1].n_r=r
way[level-1].n_c=c
search(level+1);
idx–//把刚才加进入
的字符串去掉
used[r4+c]=0
cow[4r+c]=ch
}
}
}
num[i]–
}
}
int main(void)
{
freopen(“wissqu.in”,“r”,stdin);
freopen(“wissqu.out”,“w”,stdout);
int i,j
for(i=0i<4;i++)
{
for(j=0j<4;j++)
scanf(“%c”,cow[i4+j]);
getchar();
}
#if 0
for(i=0;i<4;i++)< span="">
{
for(j=0;j<4;j++)< span="">
printf(“%c”,cow[i4+j]);
printf(“\n”);
}
#endif
sum=0
idx=0
memset(used,0,sizeof(used));
memset(num,0,sizeof(num));
search(1);
for(i=0i<16;i++)
{
printf(“%c %d %d\n“,best[i].c,best[i].n_r+1,best[i].n_c+1);
}
printf(“%d\n“,sum);
return 0
}
ID:qcx97811
LANG:C
TASK:wissqu
/
#include
#include
#include
#include
char cow[66];//原矩阵
char goal[6]={3,3,3,4,3};//最终牛群
char now[6],num[6];//now是搜索结束时的牛群数 num是当前的牛群数
char used[66];//某个点是否已经是小牛了,也就是不可以换出去
typedef struct
{//结构体,c表示字符 n_r表示row n_c表示col
char c
char n_r,n_c
}Node
Node way[18],best[18];//best表示最有解 way是搜索的中间解
int sum//sum是总结过数
int idx
void check_best()
{//检查best 然后更新est
char s1[18],s2[18];
int i,j
int k
for(i=0i<16;i++)
{
if(best[i].c < way[i].c)
return ;
if(best[i].c == way[i].c)
{
if(best[i].n_r < way[i].n_r)
return ;
if(best[i].n_r == way[i].n_r)
{
if(best[i].n_c <= way[i].n_c)
return
break
}
else
break
}
else
{
break
}
}
for(i=0i<16;i++)
{
best[i]=way[i];
}
}
int can_place(int r,int c,char ch)
{//可以把ch放置在 [r,c]这个点上
int i,j
if(1==used[r4+c])
return 0
for(i=r-1i<r+2;i++)
{
if(i>=0&i<4)
{
for(j=c-1j<c+2;j++)
{
if(j>=0&j<4)
{
if(ch == cow[i4+j])
return 0
}
}
}
}
return 1
}
void search(int level)
{
int i,j
int r,c
char ch
if(level>16)
{//已经操作16次了
memset(now,0,sizeof(now));
for(i=0i<4;i++)
{
for(j=0j<4;j++)
{
now[cow[i4+j]-‘A’]++
}
}
for(i=0i<5;i++)
{
if(now[i] != goal[i])
break
}
if(5 != i)//牛群数目不对
return
if(0 == sum)
{
for(i=0i<16;i++)
best[i]=way[i];
}
else
{
check_best();
}
sum++
return ;
}
for(i=0i<5;i++)
{
if(num[i]>=goal[i])
continue//这种牛已经放置完成 不需要放置该种牛群
num[i]++
for(r=0r<4;r++)
{
for(c=0c<4;c++)
{
if(can_place(r,c,i+‘A’))
{
ch=cow[r4+c];
cow[r4+c]=i+‘A’
used[r4+c]=1
idx++
way[level-1].c=i+‘A’
way[level-1].n_r=r
way[level-1].n_c=c
search(level+1);
idx–//把刚才加进入
的字符串去掉
used[r4+c]=0
cow[4r+c]=ch
}
}
}
num[i]–
}
}
int main(void)
{
freopen(“wissqu.in”,“r”,stdin);
freopen(“wissqu.out”,“w”,stdout);
int i,j
for(i=0i<4;i++)
{
for(j=0j<4;j++)
scanf(“%c”,cow[i4+j]);
getchar();
}
#if 0
for(i=0;i<4;i++)< span="">
{
for(j=0;j<4;j++)< span="">
printf(“%c”,cow[i4+j]);
printf(“\n”);
}
#endif
sum=0
idx=0
memset(used,0,sizeof(used));
memset(num,0,sizeof(num));
search(1);
for(i=0i<16;i++)
{
printf(“%c %d %d\n“,best[i].c,best[i].n_r+1,best[i].n_c+1);
}
printf(“%d\n“,sum);
return 0
}
