usaco_clocks.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:clocks
LANG:C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
                                    //A  B  C  D  E  F  G  H  I 
int move[11][11] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
                                 ,{0, 1, 1, 0, 1, 1, 0, 0, 0, 0}// 1 ABDE
                                 ,{0, 1, 1, 1, 0, 0, 0, 0, 0, 0}// 2 ABC
                                 ,{0, 0, 1, 1, 0, 1, 1, 0, 0, 0}// 3 BCEF
                                 ,{0, 1, 0, 0, 1, 0, 0, 1, 0, 0}// 4 ADG
                                 ,{0, 0, 1, 0, 1, 1, 1, 0, 1, 0}// 5 BDEFH
                                 ,{0, 0, 0, 1, 0, 0, 1, 0, 0, 1}// 6 CFI
                                 ,{0, 0, 0, 0, 1, 1, 0, 1, 1, 0}// 7 DEGH
                                 ,{0, 0, 0, 0, 0, 0, 0, 1, 1, 1}// 8 GHI
                                 ,{0, 0, 0, 0, 0, 1, 1, 0, 1, 1}};// 9 EFHI


      
int rec[10];
int clocks[11];
int flag = false;

int DFS(int i){

 int j, k;

 if (i > 9){

  for (j = 1; j <= 9; j++){
  
   int s = clocks[j];
   for (k = 1; k <= 9; k++){
   
    s += rec[k]*move[k][j];
    s %= 4;
   }
   if (s != 0) return 0;
  }//end of for
  for (j = 1; j <= 9; j++){
  
   if (rec[j] != 0){
    if (!flag){
     for (k = 0; k < rec[j]; k++)
      if ( k == 0)
       cout << j;
      else
       cout << " " << j;
     flag = true;
    }
    else
    {
     for (k = 0; k < rec[j]; k++)
      cout << " " << j;
    }
   }//end of if
  }//end of for
  cout << endl;
  exit(0);
 }//end of if
 else
 {
     for (int k = 0; k < 4; k++){
      rec[i] = k;
      DFS(i + 1);
  }
 }
 return 0;
}

int main(){
   
 freopen("clocks.in", "r", stdin);
 freopen("clocks.out", "w", stdout);

 memset(rec, 0, sizeof(rec));

 int i, j;
 int temp;
 for (i = 1; i <= 9; i++){
  cin >> temp;
  clocks[i] = 12 - temp;
 }

 DFS(1);

 return 0;
}