首页 > 代码库 > USACO 6.4 Wisconsin Squares

USACO 6.4 Wisconsin Squares

2024-09-18 15:08:49   218人阅读

Wisconsin Squares

It‘s spring in Wisconsin and time to move the yearling calves to the yearling pasture and last year‘s yearlings to the greener pastures of the north 40.

Farmer John has five kinds of cows on his farm (abbreviations are shown in parentheses): Guernseys (A), Jerseys (B), Herefords (C), Black Angus (D), and Longhorns (E). These herds are arranged on the 16 acre pasture, one acre for each small herd, on a 4 x 4 grid (labeled with rows and columns) like this:

              1 2 3 4
             +-------
            1|A B A C
            2|D C D E
            3|B E B C
            4|C A D E

In the initial pasture layout, the herds total 3 A‘s, 3 B‘s, 4 C‘s, 3 D‘s, and 3 E‘s. This year‘s calves have one more D herd and one fewer C herd, for a total of 3 A‘s, 3 B‘s, 3 C‘s, 4 D‘s, and 3 E‘s.

FJ is extremely careful in his placement of herds onto his pasture grid. This is because when herds of the same types of cows are too close together, they misbehave: they gather near the fence and smoke cigarettes and drink milk. Herds are too close together when they are on the same square or in any of the eight adjacent squares.

Farmer John must move his old herd out of the field and his new herd into the field using his old brown Ford pickup truck, which holds one small herd at a time. He picks up a new herd, drives to a square in the yearling pasture, unloads the new herd, loads up the old herd, and drives the old herd to the north 40 where he unloads it. He repeats this operation 16 times and then drives to Zack‘s for low-fat yogurt treats and familiar wall decor.

Help Farmer John. He must choose just exactly the correct order to replace the herds so that he never puts a new herd in a square currently occupied by the same type of herd or adjacent to a square occupied by the same type of herd. Of course, once the old cows are gone and the new cows are in place, he must be careful in the future to separate herds based on the new arrangement.

Very important hint: Farmer John knows from past experience that he must move a herd of D cows first.

Find a way for Farmer John to move the yearlings to their new pasture. Print the 16 sequential herd-type/row/column movements that lead to a safe moving experience for the cows.

Calculate the total number of possible final arrangements for the 4x4 pasture and calculate the total number of ways those arrangements can be created.

PROGRAM NAME: wissqu

TIME LIMIT: 5 seconds

INPUT FORMAT

Four lines, each with four letters that denote herds.

SAMPLE INPUT (file wissqu.in)

ABAC
DCDE
BEBC
CADE

OUTPUT FORMAT

16 lines, each with a herd-type, row and column. If there are multiple solutions (and there are), you should output the solution for which the concatenated string ("D41C42A31 ... D34") of the answers is first in lexicographic order.

One more line with the total number of ways these arrangements can be created.

SAMPLE OUTPUT (file wissqu.out)

D 4 1
C 4 2
A 3 1
A 3 3
B 2 4
B 3 2
B 4 4
E 2 1
E 2 3
D 1 4
D 2 2
C 1 1
C 1 3
A 1 2
E 4 3
D 3 4
14925

——————————————————————————————————————————————————————————题解
这是一道不需要任何优化的题
然而我不断的T
是因为我没读题……
题目中不止说了八连块，还说了当前要放置小奶牛的块不能有同种类的大奶牛
所以要不要放是九个块共同决定的……
【只有一组数据点还是样例！不走心！】
  1 /*
  2 ID: ivorysi
  3 LANG: C++
  4 PROG: wissqu
  5 */
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <queue>
 10 #include <cmath>
 11 #include <set>
 12 #include <vector>
 13 #include <algorithm>
 14 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
 15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
 16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
 17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
 18 #define inf 0x5f5f5f5f
 19 #define ivorysi
 20 #define mo 97797977
 21 #define hash 974711
 22 #define base 47
 23 #define fi first
 24 #define se second
 25 #define pii pair<int,int>
 26 #define esp 1e-10
 27 typedef long long ll;
 28 using namespace std;
 29 char c[10][10];
 30 int calc[6][6][6];
 31 int dirx[]={-1,1,0,0,1,-1,-1,1,0};
 32 int diry[]={0,0,-1,1,1,-1,1,-1,0};
 33 int num[6];
 34 
 35 bool used[6][6];
 36 char tempchange[20];
 37 int row[20],col[20];
 38 int ans;
 39 bool flag;
 40 void init() {
 41     siji(i,1,4) {scanf("%s",c[i]+1);}
 42     siji(i,1,4) {
 43         siji(j,1,4) {
 44             siji(z,0,8) {
 45                 int xx=i+dirx[z],yy=j+diry[z];
 46                 if(xx>=1 && xx<=4 && yy>=1 && yy<=4) {
 47                     ++calc[xx][yy][c[i][j]-‘A‘+1];
 48                 }
 49             }
 50         }
 51     }
 52     siji(i,1,5) num[i]=3;
 53     ++num[4];
 54 }
 55 void PRINT() {
 56     siji(i,1,16) {
 57         printf("%c %d %d\n",tempchange[i],row[i],col[i]);
 58     }
 59 }
 60 void dfs(int dep) {
 61     if(dep>16) {
 62         ++ans;
 63         if(!flag) {PRINT();flag=1;}
 64         return;
 65     }
 66     siji(z,1,5) {
 67          if(num[z]==0) continue;
 68         siji(i,1,4) {
 69             siji(j,1,4){
 70                 if(used[i][j]) continue;
 71                 if(calc[i][j][z]==0) {
 72                     used[i][j]=1;
 73                     --num[z];
 74                     siji(k,0,8) {
 75                         int xx=i+dirx[k],yy=j+diry[k];
 76                         if(xx>=1 && xx<=4 && yy>=1 && yy<=4) {
 77                             --calc[xx][yy][c[i][j]-‘A‘+1];
 78                             ++calc[xx][yy][z];
 79                         }    
 80                     }
 81                     if(!flag) {
 82                         tempchange[dep]=‘A‘+z-1;
 83                         row[dep]=i;
 84                         col[dep]=j;
 85                     }
 86                     
 87                     dfs(dep+1);
 88                     used[i][j]=0;
 89                     ++num[z];
 90                     siji(k,0,8) {
 91                         int xx=i+dirx[k],yy=j+diry[k];
 92                         if(xx>=1 && xx<=4 && yy>=1 && yy<=4) {
 93                             ++calc[xx][yy][c[i][j]-‘A‘+1];
 94                             --calc[xx][yy][z];
 95                         }    
 96                     }
 97                 }
 98             }
 99         }
100     }
101 
102 }
103 void solve() {
104     init();
105     siji(i,1,4) {
106         siji(j,1,4) {
107             if(calc[i][j][4]==0) {
108                 used[i][j]=1;
109                 --num[4];
110                 siji(k,0,8) {
111                     int xx=i+dirx[k],yy=j+diry[k];
112                     if(xx>=1 && xx<=4 && yy>=1 && yy<=4) {
113                         --calc[xx][yy][c[i][j]-‘A‘+1];
114                         ++calc[xx][yy][4];
115                     }    
116                 }
117                 if(!flag) {
118                     tempchange[1]=‘D‘;
119                     row[1]=i;
120                     col[1]=j;
121                 }
122                 dfs(2);
123                 used[i][j]=0;
124                 ++num[4];
125                 siji(k,0,8) {
126                     int xx=i+dirx[k],yy=j+diry[k];
127                     if(xx>=1 && xx<=4 && yy>=1 && yy<=4) {
128                         ++calc[xx][yy][c[i][j]-‘A‘+1];
129                         --calc[xx][yy][4];
130                     }    
131                 }
132             }
133         }
134     }
135     printf("%d\n",ans);
136 }
137 int main(int argc, char const *argv[])
138 {
139 #ifdef ivorysi
140     freopen("wissqu.in","r",stdin);
141     freopen("wissqu.out","w",stdout);
142 #else
143     freopen("f1.in","r",stdin);
144 #endif
145     solve();
146     return 0;
147 }

 

 

USACO 6.4 Wisconsin Squares


联系
我们