Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u

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

Source


思路:爆搜,由于每种操作最多进行3次(再多了没意义),所以可以枚举操作的次数,得到状态后判断是否符合条件,符合就输出。
ps:神TM爆搜,代码美如画(o´・ェ・`o)
AC代码:
#include <cstdio>
using namespace std;
int init[10], now[10];
void input()
{
	for (int i = 1; i <= 9; i++)
		scanf("%d", &init[i]);
}
void solve()
{
	int go[10];
	for (go[1] = 0; go[1] < 4; go[1]++)
		for (go[2] = 0; go[2] < 4; go[2]++)
			for (go[3] = 0; go[3] < 4; go[3]++)
				for (go[4] = 0; go[4] < 4; go[4]++)
					for (go[5] = 0; go[5] < 4; go[5]++)
						for (go[6] = 0; go[6] < 4; go[6]++)
							for (go[7] = 0; go[7] < 4; go[7]++)
								for (go[8] = 0; go[8] < 4; go[8]++)
									for (go[9] = 0; go[9] < 4; go[9]++)
									{
										now[1] = (init[1] + go[1] + go[2] + go[4]) % 4;
										now[2] = (init[2] + go[1] + go[2] + go[3] + go[5]) % 4;
										now[3] = (init[3] + go[2] + go[3] + go[6]) % 4;
										now[4] = (init[4] + go[1] + go[4] + go[5] + go[7]) % 4;
										now[5] = (init[5] + go[1] + go[3] + go[5] + go[7] + go[9]) % 4;
										now[6] = (init[6] + go[3] + go[5] + go[6] + go[9]) % 4;
										now[7] = (init[7] + go[4] + go[7] + go[8]) % 4;
										now[8] = (init[8] + go[5] + go[7] + go[8] + go[9]) % 4;
										now[9] = (init[9] + go[6] + go[8] + go[9]) % 4;
										if (!now[1] && !now[2] && !now[3] && !now[4] && !now[5] && !now[6] && !now[7] && !now[8] && !now[9])
										{
											while (go[1]--)
												printf("1 ");
											while (go[2]--)
												printf("2 ");
											while (go[3]--)
												printf("3 ");
											while (go[4]--)
												printf("4 ");
											while (go[5]--)
												printf("5 ");
											while (go[6]--)
												printf("6 ");
											while (go[7]--)
												printf("7 ");
											while (go[8]--)
												printf("8 ");
											while (go[9]--)
												printf("9 ");
											printf("\n");
											return;
										}
									}
}
int main()
{
	input();
	solve();
	return 0;
}

 

分类: ACM/ICPC

发表评论

电子邮件地址不会被公开。 必填项已用*标注