POJ 1166：The Clocks
2024-09-06 03:49:41
The Clocks
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 15357 | Accepted: 6230 |
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
最近在做高斯消元的专题，再一次感觉智商不够用，各种不爽。
这个题目就是不爽之一。。。题意是有9个表，每个表用0 1 2 3 表示这个指针的状态，然后有9种操作，每个操作包含的字母其含义代表把对应位置上的表指针顺时针拨动90度。问最终要通过什么方式让9个表都是0状态。
一开始没有想到是高斯消元。然后想了想，发现这个题目每个操作最多就3次，4次就和没有操作是一样的了。然后还有一点是与操作的顺序没有关系。于是就写了一个九层循环的暴力。。。
代码：
#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std; int val[15];
int num[15]; int main()
{
//freopen("i.txt", "r", stdin);
//freopen("o.txt", "w", stdout); int i, sum;
int i1, i2, i3, i4, i5, i6, i7, i8, i9;
int j1, j2, j3, j4, j5, j6, j7, j8, j9; for (i = 1; i <= 9; i++)
scanf("%d", &val[i]); for (i1 = 0; i1 < 4; i1++)
{
for (i2 = 0; i2 < 4; i2++)
{
for (i3 = 0; i3 < 4; i3++)
{
for (i4 = 0; i4 < 4; i4++)
{
for (i5 = 0; i5 < 4; i5++)
{
for (i6 = 0; i6 < 4; i6++)
{
for (i7 = 0; i7 < 4; i7++)
{
for (i8 = 0; i8 < 4; i8++)
{
for (i9 = 0; i9 < 4; i9++)
{
num[1] = (val[1] + i1 + i2 + i4) % 4;
num[2] = (val[2] + i1 + i2 + i3 + i5) % 4;
num[3] = (val[3] + i2 + i3 + i6) % 4;
num[4] = (val[4] + i1 + i4 + i5 + i7) % 4;
num[5] = (val[5] + i1 + i3 + i5 + i7 + i9) % 4;
num[6] = (val[6] + i3 + i5 + i6 + i9) % 4;
num[7] = (val[7] + i4 + i7 + i8) % 4;
num[8] = (val[8] + i5 + i7 + i8 + i9) % 4;
num[9] = (val[9] + i6 + i8 + i9) % 4; sum = 0;
for (i = 1; i <= 9; i++)
sum += num[i];
if (sum == 0)
{
for (j1 = 1; j1 <= i1; j1++)printf("1 ");
for (j2 = 1; j2 <= i2; j2++)printf("2 ");
for (j3 = 1; j3 <= i3; j3++)printf("3 ");
for (j4 = 1; j4 <= i4; j4++)printf("4 ");
for (j5 = 1; j5 <= i5; j5++)printf("5 ");
for (j6 = 1; j6 <= i6; j6++)printf("6 ");
for (j7 = 1; j7 <= i7; j7++)printf("7 ");
for (j8 = 1; j8 <= i8; j8++)printf("8 ");
for (j9 = 1; j9 <= i9; j9++)printf("9 ");
return 0;
}
}
}
}
}
}
}
}
}
}
//system("pause");
return 0;
}
后来发现里面的就是高斯消元列一个mod4的方程组，唉，踏踏实实下来好好提高自己吧，别眼高手低了。
高斯消元解法，4不是质数，所以高斯消元里面要改动一些，不能再每列种寻找最大值了，找到不为0的直接跳出。
代码：
#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std; int x[15];
int num[15];
int val[15][25];
bool free_x[305];//标记是否是不确定的变元 inline int gcd(int a, int b)
{
int t;
while (b != 0)
{
t = b;
b = a%b;
a = t;
}
return a;
} inline int lcm(int a, int b)
{
return a / gcd(a, b)*b;//先除后乘防溢出
} int Gauss(int equ, int var)
{
int i, j, k;
int max_r;//当前这列绝对值最大的行
int col;//当前处理的列
int ta, tb;
int LCM;
int temp;
int free_x_num;
int free_index; for (int i = 0; i <= var; i++)
{
x[i] = 0;
free_x[i] = true;
}
//转换为阶梯阵
col = 0;//当前处理的列
for (k = 0; k < equ&&col < var; k++, col++)
{
//枚举当前处理的行
max_r = k;
for (max_r = k; max_r < equ; max_r++)//改动在这里！！！！！
{
if (abs(val[max_r][col]))
{
break;
}
}
if (max_r != k)
{//与第k行交换
for (j = k; j < var + 1; j++)
swap(val[k][j], val[max_r][j]);
}
if (val[k][col] == 0)
{
k--;
continue;
}
for (i = k + 1; i < equ; i++)
{//枚举要删去的行
if (val[i][col] != 0)
{
ta = abs(val[k][col]);
tb = abs(val[i][col]);
if (val[i][col] * val[k][col] < 0)
tb = -tb; for (j = col; j < var + 1; j++)
{
val[i][j] = (((val[i][j] * ta) % 4 - (val[k][j] * tb) % 4) % 4 + 4) % 4;
}
}
}
}
for (i = var - 1; i >= 0; i--)
{
temp = val[i][var];
for (j = i + 1; j < var; j++)
{
if (val[i][j] != 0)
{
temp = temp - (val[i][j] * x[j]) % 4;
temp = (temp % 4 + 4) % 4;
}
}
for (x[i] = 0; x[i] < 4; x[i]++)
{
if ((x[i] * val[i][i] + 4) % 4 == temp)
{
break;
}
}
}
return 0;
}
int main()
{
//freopen("i.txt", "r", stdin);
//freopen("o.txt", "w", stdout); int i, sum;
int j1, j2, j3, j4, j5, j6, j7, j8, j9; for (i = 1; i <= 9; i++)
scanf("%d", &num[i]); memset(val, 0, sizeof(val));
for (i = 0; i < 9; i++)
{
val[i][9] = (4 - num[i + 1]) % 4;
if (i == 0)
{
val[i][0] = 1;
val[i][1] = 1;
val[i][3] = 1;
}
else if (i == 1)
{
val[i][0] = 1;
val[i][1] = 1;
val[i][2] = 1;
val[i][4] = 1;
}
else if (i == 2)
{
val[i][1] = 1;
val[i][2] = 1;
val[i][5] = 1;
}
else if (i == 3)
{
val[i][0] = 1;
val[i][3] = 1;
val[i][4] = 1;
val[i][6] = 1;
}
else if (i == 4)
{
val[i][0] = 1;
val[i][2] = 1;
val[i][4] = 1;
val[i][6] = 1;
val[i][8] = 1;
}
else if (i == 5)
{
val[i][2] = 1;
val[i][4] = 1;
val[i][5] = 1;
val[i][8] = 1;
}
else if (i == 6)
{
val[i][3] = 1;
val[i][6] = 1;
val[i][7] = 1;
}
else if (i == 7)
{
val[i][4] = 1;
val[i][6] = 1;
val[i][7] = 1;
val[i][8] = 1;
}
else if (i == 8)
{
val[i][5] = 1;
val[i][7] = 1;
val[i][8] = 1;
}
} Gauss(9, 9); for (j1 = 1; j1 <= x[0]; j1++)printf("1 ");
for (j2 = 1; j2 <= x[1]; j2++)printf("2 ");
for (j3 = 1; j3 <= x[2]; j3++)printf("3 ");
for (j4 = 1; j4 <= x[3]; j4++)printf("4 ");
for (j5 = 1; j5 <= x[4]; j5++)printf("5 ");
for (j6 = 1; j6 <= x[5]; j6++)printf("6 ");
for (j7 = 1; j7 <= x[6]; j7++)printf("7 ");
for (j8 = 1; j8 <= x[7]; j8++)printf("8 ");
for (j9 = 1; j9 <= x[8]; j9++)printf("9 "); //system("pause");
return 0;
}
最新文章
- Unity贴图锯齿
- web项目中，视图层中关于相对路径和绝对路径
- Effective C++ -----条款17：以独立语句将newed对象置入智能指针
- jquery check box
- VS2010之MFC串口通信的编写教程
- Android操作系统11种传感器介绍
- Guava文档翻译之ListenableFuture
- Redis配置不当可导致服务器被控制，已有多个网站受到影响 #通用程序安全预警#
- SQL ---指令实例语句
- phpcms和php格式化时间戳
- C语言中的sizeof解析
- 第52章：Java操作MongoDB-[Mongo-Java-3.x]
- 10.scrapy框架简介和基础应用
- openERP笔记 自定义模块开发
- eclipse选中某个字段没法高亮其他相同字段
- 【Hibernate步步为营】--最后的集合映射
- 008-spring cloud gateway-路由谓词RoutePredicate、RoutePredicateFactory
- 【面向对象】用大白话扯扯那"神奇"的面向对象编程思维（二）
- python包管理工具pip
- atitit.验证码识别step3----去除边框---- 图像处理类库 attilax总结java版本