|
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 閱讀(289)
評論(0) 編輯 收藏 引用 所屬分類:
搜索