soj 1171 —The Game of Efil
soj 1014 —Specialized Four-Dig
soj 1709 —PropBot
soj 1108 —Online Selection
soj 1471 —No Left Turns
soj 1710 —Painted Calculator
soj 7144 —Different Triangles
⭐⭐1
2
3
4
5
6题号：soj 1171 --The Game of Efil
题目：细胞生命游戏在一个矩形的单元格场上进行，每个单元格都有八个邻居（相邻的单元格）。一个单元只有被占用和不被占用两种状态。从上一代产生一代的规则是：
· 如果一个被占用的小区有0、1、4、5、6、7或8个被占用的邻居，则该生物死亡（0、1：孤独； 4至8：过度拥挤）。
· 如果一个被占用的细胞有两个或三个被占用的邻居，则该生物可以存活到下一个世代。
· 如果一个未被占用的小区具有三个被占用的邻居，则该小区将被占用（即产生下一代）。
给定一个初始配置，它可以有多少种父配置？
因为问题规模限制比较小，所以可以直接使用暴力枚举所有可能状态，通过深度优先搜索每次得到一种状态，再根据题目给出的规则计算得到该状态的子状态，将子状态与当前状态比较，如果完全一致，则该状态是当前状态的祖先之一。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
int row, col, ancestors;
int cells[SIZE][SIZE];
int search[SIZE][SIZE];
int to_x[DIRECTION] = { -1,0,1,-1,1,-1,0,1 };
int to_y[DIRECTION] = { -1,-1,-1,0,0,1,1,1 };
void calculate() {
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
int neighbors = 0;
for (int k = 0; k < DIRECTION; ++k) {
if (search[(i + to_x[k] + row) % row][(j + to_y[k] + col) % col] == 1)
++neighbors;
}
int cell;
if (neighbors == 3 || (search[i][j] == 1 && (neighbors == 2 || neighbors == 3)))
cell = 1;
else cell = 0;
if (cells[i][j] != cell) return;
}
}
++ancestors;
return;
}
void dfs(int x, int y) {
if (x == row) calculate();
else {
search[x][y] = 0;
if (y == col - 1) dfs(x + 1, 0);
else dfs(x, y + 1);
search[x][y] = 1;
if (y == col - 1) dfs(x + 1, 0);
else dfs(x, y + 1);
}
return;
}
int main() {
int count = 1;
while (cin >> row >> col && row && col) {
int k;
cin >> k;
int x, y;
memset(cells, 0, sizeof(cells));
while (k--) {
cin >> x >> y;
cells[x][y] = 1;
}
ancestors = 0;
memset(search, 0, sizeof(search));
dfs(0, 0);
if (ancestors)
cout << "Case " << count << ": " << ancestors << " possible ancestors." << endl;
else
cout << "Case " << count << ": Garden of Eden." << endl;
++count;
}
return 0;
}
⭐⭐1
2题号：soj 1014 --Specialized Four-Dig
题目：查找并列出所有以十进制表示法表示的符合以下规则的四位数字：该四位数的和等于其以十六进制表示时的数字之和，且以十二进制表示时也等于其数字的总和。
由于题目限制四位数并提示第一个数为2992，故直接对2992~9999的每个数分别计算它们的十进制、十二进制和十六进制各个数字之和并进行比较。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int cal(int cur, int index) {
int sum = 0;
for (int i = 0; i < 4; ++i) {
sum += (cur % index);
cur /= index;
if (cur == 0) break;
}
return sum;
}
bool judge(int num) {
int temp = num;
int sum10 = cal(num, 10), sum12 = cal(num, 12), sum16 = cal(num, 16);
return (sum10 == sum12) && (sum12 == sum16);
}
int main() {
for (int i = 2992; i < 10000; ++i) {
if (judge(i)) cout << i << endl;
}
return 0;
}
⭐⭐1
2
3题号：soj 1709 --PropBot
题目：PropBot只能做出两个不同的动作：向前移动10厘米，或向右旋转45度。这些单个动作中的每个动作都花费一秒钟的时间。
给定平面上一点的坐标和可以用来移动的最大秒数，求PropBot与目标点在给定时间内可以达到的最近距离。开始时PropBot位于原点并指向 +x 方向。
题目要求的输出看上去似乎是求解最短路径，实际上如果不遍历所有可能解的话并不能确定这个最小量，因为Propbot最终能到达的点并不是已知的确定点，而是以终点为中心的一定范围内的点，只有遍历所有的可能性才能确定最接近终点的点集。因此，选用深度优先搜索更合适。
具体做法是每走到一个点都考虑直走和右转45度以达到下一个点的情况，在搜索过程中更新达到目标点的最小距离，直到所有可能路径的终点都无法再靠近目标点（剩余时间为零或者行动一步的距离超过了当前点到目标点的直线距离）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
double MUL = sqrt(2) / 2;
int seconds;
double x, y, min_dis;
struct Node {
double x, y;
Node() {
x = y = 0;
}
Node(double X, double Y) {
x = X;
y = Y;
}
};
Node target;
double dis(Node n1, Node n2) {
return sqrt((n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y));
}
void dfs(Node cur, int dir, int time) {//dir: 0 presents +x and rotate clockwise.
double temp = dis(cur, target);
dir %= 8;
min_dis = min(min_dis, temp);
if (time == seconds) return;
if (temp - 10 * (seconds - time) > min_dis) return;
switch (dir){
case 0:
dfs(Node(cur.x + 10, cur.y), 0, time + 1);
break;
case 1:
dfs(Node(cur.x + MUL * 10, cur.y - MUL * 10), 1, time + 1);
break;
case 2:
dfs(Node(cur.x, cur.y - 10), 2, time + 1);
break;
case 3:
dfs(Node(cur.x - MUL * 10, cur.y - MUL * 10), 3, time + 1);
break;
case 4:
dfs(Node(cur.x - 10, cur.y), 4, time + 1);
break;
case 5:
dfs(Node(cur.x - MUL * 10, cur.y + MUL * 10), 5, time + 1);
break;
case 6:
dfs(Node(cur.x, cur.y + 10), 6, time + 1);
break;
case 7:
dfs(Node(cur.x + MUL * 10, cur.y + MUL * 10), 7, time + 1);
break;
}
dfs(cur, dir + 1, time + 1);
return;
}
int main() {
int cases;
cin >> cases;
while (cases--) {
cin >> seconds >> x >> y;
target = Node(x, y);
Node start(0, 0);
min_dis = dis(start, target);
dfs(start, 0, 0);
cout << fixed << setprecision(6) << min_dis << endl;
}
return 0;
}
⭐⭐1
2
3题号：soj 1108 --Online Selection
题目：节目组有0到n-1共n组问题，每组问题的答案相同，并且每个问题的答案只有0、1两种。一开始参与者的状态是0，拥有0分。在状态i的参与者被给出第i组中的一个问题，如果参与者答对问题，那么分数加1。另外如果参与者回答的是0，状态i就会转移到状态i0，回答的是1，则转移到状态i1。
给定第i组的问题的答案，以及i0和i1，并且已知这个过程持续了k轮，选手得到了m分，求在这个过程中，选手回答0的次数最多的情况。
用dp[i][j][m]表示当当前状态为i、已响应次数为j、当前得分为m时“0”响应总数的最大值。在互动过程中，候选人的状态、得分和“0”响应总数始终依赖于上一次互动的情况，那么可以考虑从初始状态开始每次都向状态i0和i1进行记忆化搜索。状态转移方程如下：
边界条件：
1 |
|
⭐⭐1
2题号：soj 1471 --No Left Turns
题目：一个迷宫，从起点走到终点，每一步有直走和直走再右转两个选择（注意不能原地转弯），问在这种情况下的最短路径是多少。已知起始方向可以任意选择，且保证这样的路径一定存在。
当尝试向不同方向前进时，若条件满足（朝向正确、不碰墙壁），则每前进一步，路径长度加1。基于上述设定，应该选择广度优先搜索。初始时将起点位置满需条件的不同朝向的状态送入队列，搜索过程中考虑朝向不变和右转两种情况，首次搜索到终点的路径即是最短路径。要注意输入的字符有空格。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
using namespace std;
int row, column;
int start_x , start_y;
char puzzle[SIZE][SIZE];
int to_x[DIRECTION] = {0, -1, 0, 1};
int to_y[DIRECTION] = {-1, 0, 1, 0};
int dis[SIZE][SIZE][DIRECTION];//N W S E
int visit[SIZE][SIZE][DIRECTION];
struct Node {
int x, y, d;
Node() {
x = y = d = 0;
}
Node(int X, int Y, int D) {
x = X;
y = Y;
d = D;
}
};
int bfs() {
queue<Node> q;
for (int i = 0; i < 4; ++i) {
if (puzzle[start_x + to_x[i]][start_y + to_y[i]] != 'X') {
Node temp(start_x, start_y, i);
q.push(temp);
dis[temp.x][temp.y][temp.d] = 0;
visit[temp.x][temp.y][temp.d] = 1;
}
}
while (!q.empty()) {
Node temp = q.front();
q.pop();
Node next;
for (int i = 0; i < 2; ++i) {
if (i == 0) {
next.d = temp.d;
}
else {
next.d = (temp.d + 1) % 4;
}
int next_x = temp.x + to_x[next.d];
int next_y = temp.y + to_y[next.d];
if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < column) {
if (puzzle[next_x][next_y] != 'X' && (!visit[next_x][next_y][next.d])) {
if (puzzle[next_x][next_y] == 'F') return dis[temp.x][temp.y][temp.d] + 1;
visit[next_x][next_y][next.d] = 1;
dis[next_x][next_y][next.d] = dis[temp.x][temp.y][temp.d] + 1;
next.x = next_x;
next.y = next_y;
q.push(next);
}
}
}
}
}
int main() {
int N;
cin >> N;
while (N--) {
cin >> row >> column;
for (int i = 0; i < row; ++i) {
getchar();
for (int j = 0; j < column; ++j) {
cin.get(puzzle[i][j]);
if (puzzle[i][j] == 'S') {
start_x = i;
start_y = j;
}
}
}
memset(dis, -1, sizeof(dis));
memset(visit, 0, sizeof(visit));
cout << bfs() << endl;
}
return 0;
}
⭐⭐1
2题号：soj 1710 --Painted Calculator
题目：计算器中，一个数的一个译码管亮起需要消耗5毫安，如果是负数的话，那个负号需要单独消耗5毫安。已知运用这个计算器进行了一个四则运算(a ? b = c形式，且如果所做的运算是除法则b不为0)，得到每个数的功耗，问一共有多少个这样的运算满足条件。已知每个数绝对值都小于1000。
对每一项输入，暴力搜索匹配的数字组合，并枚举四则运算进行验证。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using namespace std;
int MA[10] = {30, 10, 25, 25, 20, 25, 30, 15, 35, 30};// 0 - 9
int getMA(int num) {
int res = 0;
if (num == 0) return MA[0];
if (num < 0) res += 5;
num = abs(num);
while (num) {
res += MA[num % 10];
num /= 10;
}
return res;
}
int main() {
int x, y, z;
while (cin >> x && x) {
cin >> y >> z;
if ((x > 110 || y > 110 || z > 110) || (x % 5 != 0 || y % 5 != 0 || z % 5 != 0)) {
cout << "0 solutions for " << x << " " << y << " " << z << endl;
continue;
}
int count = 0;
for (int i = -999; i <= 999; ++i) {
int X = getMA(i);
if (X != x) continue;
for (int j = -999; j <= 999; ++j) {
int Y = getMA(j);
if (Y != y) continue;
int Z;
if (i + j >= -999 && i + j <= 999) {
Z = getMA(i + j);
if (Z == z) ++count;
}
if (i - j >= -999 && i - j <= 999) {
Z = getMA(i - j);
if (Z == z) ++count;
}
if (i * j >= -999 && i * j <= 999) {
Z = getMA(i * j);
if (Z == z) ++count;
}
if (j == 0) continue;
if (i / j >= -999 && i / j <= 999) {
Z = getMA(i / j);
if (Z == z) ++count;
}
}
}
if (count == 1) cout << "1 solution for " << x << " " << y << " " << z << endl;
else cout << count << " solutions for " << x << " " << y << " " << z << endl;
}
return 0;
}
⭐⭐1
2题号：soj 7144 --Different Triangles
题目：给出n根棍子的长度(n<=100)，求出用其中的三根棍子可以摆出的三角形的个数。
问题规模较小，直接使用枚举，对sticks数组排序可以适当减少循环次数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
int main() {
int cases;
cin >> cases;
while (cases--) {
int num, sticks[101];
cin >> num;
for (int i = 0; i < num; ++i) {
cin >> sticks[i];
}
sort(sticks, sticks + num);
int sum = 0;
for (int i = 0; i < num; ++i) {
for (int j = i + 1; j < num; ++j) {
for (int k = j + 1; k < num; ++k) {
if (sticks[k] >= sticks[i] + sticks[j]) break;
else ++sum;
}
}
}
cout << sum << endl;
}
return 0;
}