小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o
表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。 数据保证答案一定有解。
输入样例1：
输出样例1：
输入样例2：
1
2
| *o**o***o***
*o***o**o***
|
输出样例2：
分析
贪心：如果当前位置不同，那就要翻转当前位置和当前位置的下一位，而当前位置之前的所有位置已经都是调整到和目标一样了
代码
暴搜(超时了)
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
| import java.util.Scanner;
public class Main {
static StringBuffer stringInitial;
static String stringTarget;
static StringBuffer stringOperation = new StringBuffer();
static int stringLen;
static int LEFT = -1;
static int RIGHT = 1;
static int steps = 0;
static int minSteps = Integer.MAX_VALUE;
static void reverse(int count) {
if(stringInitial.charAt(count) == '*') {
stringInitial.setCharAt(count, 'o');
} else {
stringInitial.setCharAt(count, '*');
}
}
static void change(int count, int direction) {
reverse(count);
reverse(count + direction);
}
static boolean valid() {
if(stringInitial.toString().equals(stringTarget)) {
return true;
} else {
return false;
}
}
static void printString() {
System.out.println(stringInitial);
}
static boolean flag = false;
static void dfs(int count) {
if(count == stringLen) {
if(valid() && steps < minSteps) {
minSteps = steps;
}
return;
}
if(count == 0) {
change(count, RIGHT);
steps += 1;
dfs(count + 1);
change(count, RIGHT);
steps--;
} else if(count == stringLen - 1) {
change(count, LEFT);
steps++;
dfs(count + 1);
change(count, LEFT);
steps--;
} else {
change(count, RIGHT);
steps++;
dfs(count + 1);
change(count, RIGHT);
steps--;
change(count, LEFT);
steps++;
dfs(count + 1);
change(count, LEFT);
steps--;
}
dfs(count + 1);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String tmpString = scan.nextLine();
stringInitial = new StringBuffer(tmpString);
stringTarget = scan.nextLine();
stringLen = stringInitial.length();
dfs(0);
System.out.println(minSteps);
scan.close();
}
}
|
贪心
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
| import java.util.Scanner;
public class Main {
static StringBuffer stringOperation;
static String stringTarget;
static void change(int count) {
if(stringOperation.charAt(count) == '*') {
stringOperation.setCharAt(count, 'o');
} else {
stringOperation.setCharAt(count, '*');
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String tmpString = scan.nextLine();
stringOperation = new StringBuffer(tmpString);
stringTarget = scan.nextLine();
int steps = 0;
for(int i = 0; i < stringTarget.length(); i++) {
if(stringOperation.charAt(i) != stringTarget.charAt(i)) {
change(i);
change(i + 1);
steps++;
}
}
System.out.println(steps);
scan.close();
}
}
|