IOI 1994 / POJ 1166: The Clocks

Problem Statement

The Clocks Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 17678 Accepted: 7258 Description

|-------|    |-------|    |-------|

|       |    |       |    |   |   |

|---O   |    |---O   |    |   O   |

|       |    |       |    |       |

|-------|    |-------|    |-------|

    A            B            C    



|-------|    |-------|    |-------|

|       |    |       |    |       |

|   O   |    |   O   |    |   O   |

|   |   |    |   |   |    |   |   |

|-------|    |-------|    |-------|

    D            E            F    



|-------|    |-------|    |-------|

|       |    |       |    |       |

|   O   |    |   O---|    |   O   |

|   |   |    |       |    |   |   |

|-------|    |-------|    |-------|

    G            H            I    

(Figure 1)

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o'clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90' (degrees) clockwise on those clocks which are affected according to figure 2 below. Move Affected clocks

1 ABDE

2 ABC

3 BCEF

4 ADG

5 BDEFH

6 CFI

7 DEGH

8 GHI

9 EFHI

(Figure 2) Input

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o'clock, 1=3 o'clock, 2=6 o'clock, 3=9 o'clock. Output

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o'clock. You are convinced that the answer is unique. Sample Input 3 3 0 2 2 2 2 1 2 Sample Output 4 5 8 9

The Algorithm

This problem uses a BFS search for the shortest-reachable solution. However, a simple BFS is way too slow. But we can still improve the O(9^n) time complexity. We can first save each state as a base-4 number (e.g. 132331201) and convert it into base 10, then save it to a hash array. Or even more simply, we can realize that a move sequence like "I J" where I and J are integers in 1~9 produces the same result as the sequence "J I", cutting down 4/9 values every round. Also, storing the different movements can be done in an array: store a 0 or 1 in the array depending on whether or not a move changes that clock. Then, iterating over a specific sub-array and adding the value, whether 0 or 1, updates the array.

The Code

#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
using namespace std;

struct cluck
{
	int a,b,c,d,e,f,g,h,i,t;
	string l;
	void operator=(cluck ot)
	{
		a=ot.a;b=ot.b;c=ot.c;d=ot.d;e=ot.e;f=ot.f;g=ot.g;h=ot.h;i=ot.i;l=ot.l;
	}
};
queue<cluck> que;

inline cluck m1(cluck a){return {++a.a%4,++a.b%4,  a.c,  ++a.d%4,++a.e%4,  a.f,    a.g,    a.h,    a.i,    1,    a.l+"1 "};}
inline cluck m2(cluck a){return {++a.a%4,++a.b%4,++a.c%4,  a.d,    a.e,    a.f,    a.g,    a.h,    a.i,    2,    a.l+"2 "};}
inline cluck m3(cluck a){return {  a.a  ,++a.b%4,++a.c%4,  a.d,  ++a.e%4,++a.f%4,  a.g,    a.h,    a.i,    3,    a.l+"3 "};}
inline cluck m4(cluck a){return {++a.a%4,  a.b,    a.c,  ++a.d%4,  a.e,    a.f,  ++a.g%4,  a.h,    a.i,    4,    a.l+"4 "};}
inline cluck m5(cluck a){return {  a.a,  ++a.b%4,  a.c,  ++a.d%4,++a.e%4,++a.f%4,  a.g,  ++a.h%4,  a.i,    5,    a.l+"5 "};}
inline cluck m6(cluck a){return {  a.a,    a.b,  ++a.c%4,  a.d,    a.e,  ++a.f%4,  a.g,    a.h,  ++a.i%4,  6,    a.l+"6 "};}
inline cluck m7(cluck a){return {  a.a,    a.b,    a.c,  ++a.d%4,++a.e%4,  a.f,  ++a.g%4,++a.h%4,  a.i,    7,    a.l+"7 "};}
inline cluck m8(cluck a){return {  a.a,    a.b,    a.c,    a.d,    a.e,    a.f,  ++a.g%4,++a.h%4,++a.i%4,  8,    a.l+"8 "};}
inline cluck m9(cluck a){return {  a.a,    a.b,    a.c,    a.d,  ++a.e%4,++a.f%4,  a.g,  ++a.h%4,++a.i%4,  9,    a.l+"9 "};}

cluck(*arr[9])(cluck) = {m1,m2,m3,m4,m5,m6,m7,m8,m9};
int cnt[10];
string bfs(cluck s)
{
	s.t=1;
	que.push(s);
	while(!que.empty())
	{
		cluck p=que.front(); que.pop();
		cnt[p.t]++;
		if(cnt[p.t]>=4){cnt[p.t]--;continue;}
		if(p.a==0&&p.b==0&&p.c==0&&p.d==0&&p.e==0&&p.f==0&&p.g==0&&p.h==0&&p.i==0) return p.l;
		for(int i=p.t-1;i<9;i++)que.push(arr[i](p));
		cnt[p.t]--;
	}
	return "NO";
}

int main()
{
	cluck a;
	scanf("%d %d %d %d %d %d %d %d %d",&a.a,&a.b,&a.c,&a.d,&a.e,&a.f,&a.g,&a.h,&a.i);
	string s=bfs(a); s.erase(s.end()-1,s.end());
	cout<<s<<endl;
}