首页 > 代码库 > 8469:特殊密码锁

8469:特殊密码锁

2024-10-12 20:54:02   215人阅读

传送门:http://noi.openjudge.cn/ch0406/8469/

描述

有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。

然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。

当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。

输入

两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。

输出

至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。

样例输入

011
000

样例输出

1

然而并没有AC，求dalao纠察Orz
 1 /////////////////////////
 2 //
 3 //6-27   PAx: Homii_wors
 4 //
 5 //Name:  N8469 Spacikeys
 6 //
 7 //Solut: NP  &DFS W.A.
 8 //
 9 /////////////////////////
10 //#include "stdafx.h"
11 #include <bits/stdc++.h>
12 using namespace std;
13 int be[3][31], af[31], n = 0, N = 0;
14 inline void pro(int x, int d)
15 {
16     be[d][x] = !be[d][x];
17     be[d][x + 1] = !be[d][x + 1];
18     be[d][x + 2] = !be[d][x + 2];
19     be[d][0] += 1;
20 }
21 int main()
22 {
23     char in;
24     while (in = getchar())
25     {
26         if (in == ‘\n‘ || in == ‘\r‘) break;
27         if (in != ‘ ‘) be[1][++n] = in - ‘0‘;
28     }
29     while (in = getchar())
30     {
31         if (in == ‘\n‘ || in == ‘\r‘) break;
32         if (in != ‘ ‘) af[++N] = in - ‘0‘;
33     }
34     //***************************************
35     be[2][0] = -1;
36     if (be[1][1] != af[1])
37     {
38         be[2][0] = 1;
39         for (int i = 1; i <= n; i++)
40             be[2][i] = be[1][i];
42         for (int i = 0; i <= n - 1; i++)
43             if (be[2][i] != af[i])
44                 pro(i, 2);
45         if (be[2][n] != af[n])
46             be[2][0] = -1;
47     }
48     for (int i = 1; i <= n - 1; i++)
49         if (be[1][i] != af[i])
50             pro(i, 1);
51     if (be[1][n] != af[n])
52         be[1][0] = -1;
53     //***************************************
54     int ans = (1 << 30);
55     for (int i = 1; i <= 2; i++)
56         if (be[i][0] != -1)
57             ans = ans < be[i][0] ? ans : be[i][0];
58     if (ans != (1 << 30)) printf("%d\n", ans);
59     else printf("impossible\n");
60     return 0;
61 }

 

8469:特殊密码锁


联系
我们