不容易啊~~

差点就写BFS去了 {zh1}还是活生生的用Depth First with Iterative Deepening给A掉了

爽死我了~~

砍枝很重要，还有些小优化都可以使出来。

主要的两个在usaco前面的text也提到了，一个是同一种旋转方式用了4次等于没用，另外一个就是顺序无关（所以如果{dy}次选择了第二个旋转方法，在后面的迭代（是叫迭代么？）中就不可能选择第三种、第四种……第九种）

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;
vector<int> result;
char effected_clocks[9][7] = {"ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI"};
typedef int clock_data[9];
int times[9] = {0};

void
initialize()
{
   for (int i = 0; i != 9; ++i) {
      for (int j = 0; j != 7; ++j) {
         if (effected_clocks[i][j]) {
            effected_clocks[i][j] -= 'A';
         } else {
            effected_clocks[i][j] = -1;
            break;
         }
      }
   }
}

bool
truncated_dfs(clock_data& clock_info, int depth, int max_i)
{
   if (depth) {
      for (int i = 0; i != max_i; ++i) {
         char * current_effect;

         if (times[i] == 3) {
            continue;
         }

         current_effect = effected_clocks[i];
         for (char *effect = current_effect; *effect != -1; ++effect) {
            int * temp(clock_info + *effect);
            ++(*temp);
            *temp %= 4;
         }
         ++times[i];
         if (truncated_dfs(clock_info, depth - 1, i + 1)) {
            result.push_back(i);
            return true;
         }
         --times[i];
         for (char * effect = current_effect; *effect != -1; ++effect) {
            int * temp(clock_info + *effect);

            --(*temp);
            if (*temp < 0) {
               *temp += 4;
            }
         }
      }
   } else {
      for (int i = 0; i != 9; ++i) {
         if (clock_info[i]) {
            return false;
         }
      }
      return true;
   }

   return false;
}

int
main()
{
   ofstream fout ("clocks.out");
   ifstream fin ("clocks.in");
   clock_data clock_info;
   int depth(0);

   initialize();

   for (int i = 0; i != 9; ++i) {
      int temp;

      fin >> temp;
      temp /= 3;
      temp %= 4;
      clock_info[i] = temp;
   }

   while (!truncated_dfs(clock_info, depth, 9)) {
      cout << depth;
      ++depth;
   }

   sort(result.begin(), result.end());

   if (result.size()) {
      for (vector<int>::iterator iter = result.begin(); iter != result.end() - 1; ++iter) {
         fout << *iter + 1 << " ";
      }
      fout << *(result.end() - 1) + 1 << endl;
   } else {
      fout << endl;
   }

   return 0;
}