|
Problem description
|
There are two binary strings, their length is 8, you should change the first to the second through several approach. You need output the minimal steps to change them.
These are the approach legle:
1.Make the whole string one step to right,the first position should be '1'.
Example: 10001100---->11000110;
2.Change two character nearby.
Example: 10010001---->10001001;
3.Change four series '1' to '0',or four series '0' to '1'.If the series character longer than four,you can change any four series characters of them.
Example: 00111101---->00000001;10000011---->11111011;
|
|
Input
|
There are many test cases.Every test case contain two 8-binary string,division by space.
|
|
Output
|
Every line output a number for the minimal steps to change the two strings.
|
|
Sample Input
|
00011110 10000000
|
|
Sample Output
|
2
|
广度搜索：
1
#include
<
iostream
>
2
#include
<
queue
>
3
#include
<
algorithm
>
4
using
namespace
std;
5
bool
mark[
256
];
6
int
binary[
8
]
=
{
1
,
2
,
4
,
8
,
16
,
32
,
64
,
128
}
;
7
struct
Node
8
{
9
int
steps;
10
char
states[
9
];
11
Node()
12
{}
13
Node(
int
s,
char
str[
9
] )
14
:steps(s)
15
{
16
strcpy( states, str );
17
}
18
}
;
19
int
getn(
char
*
str )
20
{
21
int
total
=
0
;
22
for
(
int
i
=
0
; i
<
8
;
++
i )
23
total
+=
( ( str[i]
-
'
0
'
)
*
binary[
7
-
i] );
24
return
total;
25
}
26
int
numof0(
char
*
str,
int
&
pos )
27
{
28
int
max
=
0
;
29
int
i
=
0
;
30
for
(
int
i
=
0
; i
<=
4
;
++
i )
31
{
32
int
t
=
i;
33
int
total
=
0
;
34
while
( str[t]
==
'
0
'
)
35
{
36
t
++
;
37
total
++
;
38
}
39
if
( total
>
max )
40
{
41
max
=
total;
42
pos
=
i;
43
}
44
}
45
return
max;
46
}
47
int
numof1(
char
*
str,
int
&
pos )
48
{
49
int
max
=
0
;
50
int
i
=
0
;
51
for
(
int
i
=
0
; i
<=
4
;
++
i )
52
{
53
int
t
=
i;
54
int
total
=
0
;
55
while
( str[t]
==
'
1
'
)
56
{
57
t
++
;
58
total
++
;
59
}
60
if
( total
>
max )
61
{
62
max
=
total;
63
pos
=
i;
64
}
65
}
66
return
max;
67
}
68
int
main()
69
{
70
char
source[
9
];
71
char
dest[
9
];
72
while
( scanf(
"
%s%s
"
,source, dest)
!=
EOF )
73
{
74
queue
<
Node
>
q;
75
q.push ( Node(
0
,source) );
76
memset( mark,
false
,
sizeof
(mark) );
77
mark[ getn(source) ]
=
true
;
78
while
(
!
q.empty () )
79
{
80
struct
Node head
=
q.front ();
81
char
temp[
9
];
82
int
n;
83
q.pop ();
84
if
( strcmp( head.states, dest )
==
0
)
85
{
86
printf(
"
%d\n
"
,head.steps );
87
break
;
88
}
89
90
strcpy( temp, head.states );
91
for
(
int
i
=
7
; i
>
0
; i
--
)
92
temp[i]
=
temp[i
-
1
];
93
temp[
0
]
=
'
1
'
;
94
n
=
getn(temp);
95
if
(
!
mark[n] )
96
{
97
q.push ( Node( head.steps
+
1
, temp ) );
98
mark[n]
=
true
;
99
}
100
for
(
int
i
=
0
; i
<
7
;
++
i )
101
{
102
strcpy( temp, head.states );
103
if
( temp[i]
!=
temp[i
+
1
] )
104
{
105
std::swap ( temp[i], temp[i
+
1
] );
106
n
=
getn(temp);
107
if
(
!
mark[n] )
108
{
109
q.push ( Node( head.steps
+
1
, temp ) );
110
mark[n]
=
true
;
111
}
112
}
113
}
114
int
pos;
115
int
num
=
numof0( head.states, pos );
116
if
( num
>=
4
)
117
{
118
for
(
int
i
=
pos; i
<=
num
-
4
+
pos;
++
i )
119
{
120
strcpy( temp, head.states );
121
for
(
int
j
=
i; j
<
i
+
4
;
++
j )
122
temp[j]
=
'
1
'
;
123
n
=
getn(temp);
124
if
(
!
mark[n] )
125
{
126
q.push ( Node( head.steps
+
1
, temp ) );
127
mark[n]
=
true
;
128
}
129
}
130
}
131
132
num
=
numof1( head.states, pos );
133
if
( num
>=
4
)
134
{
135
for
(
int
i
=
pos; i
<=
num
-
4
+
pos;
++
i )
136
{
137
strcpy( temp, head.states );
138
for
(
int
j
=
i; j
<
i
+
4
;
++
j )
139
temp[j]
=
'
0
'
;
140
n
=
getn(temp);
141
if
(
!
mark[n] )
142
{
143
q.push ( Node( head.steps
+
1
, temp ) );
144
mark[n]
=
true
;
145
}
146
}
147
}
148
}
//
while q.empty();
149
}
150
return
0
;
151
}
152
posted on 2008-08-18 20:14
Darren 阅读(247)
评论(0) 编辑 收藏 引用 所属分类:
搜索