注册登录

问题 L: 「Usaco2005 Feb」竞选划区O(∩_∩)O 纯属的暴力

题目描述

农场被划分为5x5的格子，每个格子中都有一头奶牛，并且只有荷斯坦(标记为H)和杰尔西（标记为J）两个品种． 
如果一头奶牛在另一头上下左右四个格子中的任一格里，我们说它们相连． 奶牛要大选了．现在有一只杰尔西奶牛们想选择7头相连的奶牛，划成一个竞选区，使得其中它们品种的奶牛比荷斯坦的多．  
要求你编写一个程序求出方案总数． 

输入

输入5行农场的情况．

输出

输出1行,即划区方案总数．

样例输入 Copy

HHHHH

JHJHJ

HHHHH

HJHHJ

HHHHH
知识兔

样例输出 Copy

2
知识兔

提示

 解题思路

  •  这题感觉就是就是一个巨暴力的暴力。一开始还不敢打，后来看到是道黄题，直接暴力就过了，然后加一个优化还挺快的。。。
  • 每一次去拓展7个点，然后判断一下会可不可以，然后就可以找到答案。
  • 可以非常明显的发现，对于一张图，会有很多种拓展方法，其中必有很多重复的，然后就需要去判重。
  • 判重有很多种方法，可以hash还可以用什么set...

暴力的代码：

 1 #include<cstdio>
 2 const int mx[4]={0,1,0,-1};
 3 const int my[4]={1,0,-1,0};
 4 bool map[6][6];
 5 int d[6][6];
 6 int s[8];
 7 int nx[8],ny[8];
 8 int q[10];
 9 int ans;
10 inline bool mark()
11 {
12     int i,j,sx,sy,xx,yy,sum=0,t=0,w=1;
13     for (i=1;i<=5;i++)for(j=1;j<=5;j++)d[i][j]=0;
14     for (i=1;i<=7;i++)
15     {
16         ny[i]=s[i]%5;nx[i]=s[i]/5;
17         if (ny[i])nx[i]++;
18         if (!ny[i])ny[i]=5;
19         d[nx[i]][ny[i]]=i;
20     }
21     q[1]=1;d[nx[1]][ny[1]]=0;sum=map[nx[1]][ny[1]];
22     while (t<w)
23     {
24         xx=nx[q[++t]];
25         yy=ny[q[t]];
26         for (int k=0;k<4;k++)
27         {
28           sx=xx+mx[k];sy=yy+my[k];
29           if (sx>0&&sy>0&&sx<6&&sy<6&&d[sx][sy])
30           {
31             q[++w]=d[sx][sy];
32             d[sx][sy]=0;
33             sum+=map[sx][sy];
34           }
35         }
36     }
37     return w==7&&sum>3;
38 }
39 int main()
40 {
41     for (int i=1;i<=5;i++)
42     for (int j=1;j<=5;j++)
43     {
44         char ch=getchar();
45         while (ch!='H'&&ch!='J')ch=getchar();
46         if (ch=='J')map[i][j]=1;
47     }
48     for (s[1]=1;s[1]<=19;s[1]++)
49     for (s[2]=s[1]+1;s[2]<=20;s[2]++)
50     for (s[3]=s[2]+1;s[3]<=21;s[3]++)
51     for (s[4]=s[3]+1;s[4]<=22;s[4]++)
52     for (s[5]=s[4]+1;s[5]<=23;s[5]++)
53     for (s[6]=s[5]+1;s[6]<=24;s[6]++)
54     for (s[7]=s[6]+1;s[7]<=25;s[7]++)
55       if (mark())ans++;
56     printf("%d",ans);
57 }
知识兔View Code
计算机