1 00:00:02,540 --> 00:00:03,463 Hello 2 00:00:03,551 --> 00:00:05,425 For the lecture of data structure and algorithm, 3 00:00:05,511 --> 00:00:09,589 we continue the study of stack and queue 4 00:00:10,333 --> 00:00:13,766 We introduce an application of queue today. 5 00:00:14,295 --> 00:00:15,935 When solving the problem, 6 00:00:15,992 --> 00:00:20,064 we provide with an example of the farmer crossing the river 7 00:00:20,625 --> 00:00:24,272 农夫带着狼羊菜 The farmer takes wolf, sheep and vegetables. 8 00:00:24,344 --> 00:00:26,751 From a side to another. 9 00:00:27,313 --> 00:00:30,107 When he crosses the river by boat, 10 00:00:30,648 --> 00:00:32,880 he can take only one passenger. 11 00:00:33,461 --> 00:00:35,052 When he is not there, 12 00:00:35,665 --> 00:00:37,402 golf and sheep, sheep and vegetable 13 00:00:37,481 --> 00:00:39,118 can not stay together alone. 14 00:00:39,856 --> 00:00:43,058 From the aspect of start side, 15 00:00:43,138 --> 00:00:46,959 I list the ten reasonable 16 00:00:47,015 --> 00:00:48,022 status of start side. 17 00:00:48,503 --> 00:00:49,444 Then 18 00:00:50,082 --> 00:00:52,397 the farmer takes a thing 19 00:00:52,466 --> 00:00:54,190 or nothing 20 00:00:54,266 --> 00:00:56,553 from a side to a nother 21 00:00:56,633 --> 00:00:59,833 and from the connections between 22 00:00:59,921 --> 00:01:01,231 these status. 23 00:01:02,746 --> 00:01:04,841 In this solving process, 24 00:01:04,905 --> 00:01:09,483 we start from the start node 25 00:01:09,559 --> 00:01:10,831 of man, sheep, wolf and vegetable 26 00:01:10,887 --> 00:01:13,950 to the end when they goes to the other side, 27 00:01:14,014 --> 00:01:15,625 while the start node 28 00:01:15,700 --> 00:01:17,033 is empty. 29 00:01:17,104 --> 00:01:20,042 To find such reachable path. 30 00:01:21,526 --> 00:01:24,197 In chapter 7 graph, 31 00:01:24,269 --> 00:01:27,167 we introduce the shortest 32 00:01:27,247 --> 00:01:28,449 Dijkstra algorithm 33 00:01:28,513 --> 00:01:30,482 to solve this problem. 34 00:01:30,866 --> 00:01:34,138 We change an aspect to think of the problem. 35 00:01:34,218 --> 00:01:37,796 we can use a bit vector 36 00:01:37,876 --> 00:01:43,430 to express man, sheep, wolf, vegetable. 37 00:01:43,510 --> 00:01:47,948 whether they are at the start side or the other. 38 00:01:48,027 --> 00:01:50,589 It is 0 at the start side, 39 00:01:50,669 --> 00:01:53,319 and 1 at the other one. 40 00:01:53,982 --> 00:01:54,934 So that 41 00:01:55,031 --> 00:01:59,244 we goes from the initialized 0000 42 00:01:59,355 --> 00:02:00,947 such a status 43 00:02:01,554 --> 00:02:04,383 through some transference 44 00:02:04,463 --> 00:02:07,281 to the status of 1111 45 00:02:07,337 --> 00:02:09,766 such a goal. 46 00:02:11,544 --> 00:02:13,931 For such a status transfer space 47 00:02:13,995 --> 00:02:16,998 how do we 48 00:02:17,086 --> 00:02:19,058 solve the problem. 49 00:02:19,791 --> 00:02:22,505 In general, we have two methods. 50 00:02:23,081 --> 00:02:25,632 The first is depth-first search. 51 00:02:26,433 --> 00:02:29,579 like the Queen Problem. 52 00:02:29,667 --> 00:02:34,521 When I put a queen in the first line, 53 00:02:34,609 --> 00:02:37,041 I look at a position at the second line 54 00:02:37,105 --> 00:02:37,867 to see whether I can put it there. 55 00:02:37,947 --> 00:02:39,500 If so, 56 00:02:39,580 --> 00:02:42,372 we continue to the third line. 57 00:02:42,457 --> 00:02:43,460 If not, 58 00:02:43,548 --> 00:02:45,648 I change to another position. 59 00:02:45,746 --> 00:02:47,453 If at a line, 60 00:02:47,541 --> 00:02:49,216 there is no position to put. 61 00:02:49,312 --> 00:02:52,405 Then I go back to the last line. 62 00:02:52,475 --> 00:02:54,954 to see if I can change the position. 63 00:02:55,042 --> 00:02:56,583 If not, 64 00:02:56,655 --> 00:02:58,019 we goes back level by level. 65 00:02:58,107 --> 00:02:59,922 until the first line, maybe. 66 00:02:59,994 --> 00:03:02,511 to change the position. 67 00:03:03,214 --> 00:03:04,035 This process 68 00:03:04,115 --> 00:03:06,688 is depth-first. 69 00:03:06,772 --> 00:03:09,235 If we look at the status space, 70 00:03:09,308 --> 00:03:11,862 it starts from a node 71 00:03:11,943 --> 00:03:14,197 along a branch 72 00:03:14,269 --> 00:03:15,700 and goes down. 73 00:03:15,789 --> 00:03:16,848 until the end. 74 00:03:16,962 --> 00:03:19,478 Then I change the position in the same level. 75 00:03:19,549 --> 00:03:22,724 If I can not change at this level, 76 00:03:22,803 --> 00:03:25,214 I go up back. 77 00:03:25,286 --> 00:03:29,345 And find another status there. 78 00:03:29,413 --> 00:03:32,351 This is a method of depth-first. 79 00:03:32,442 --> 00:03:35,771 We can use stack to realize it. 80 00:03:35,857 --> 00:03:38,522 Or use a stack. 81 00:03:39,288 --> 00:03:40,000 Here, we 82 00:03:40,082 --> 00:03:42,495 introduce a method of width-first search. 83 00:03:43,168 --> 00:03:44,231 The width-first search 84 00:03:44,319 --> 00:03:48,853 is that I put every status at the top 85 00:03:48,949 --> 00:03:53,270 into a queue. 86 00:03:53,342 --> 00:03:54,559 Then 87 00:03:54,638 --> 00:03:58,449 we push a node from the front of the node. 88 00:03:58,537 --> 00:04:01,115 For the next node 89 00:04:01,187 --> 00:04:02,699 the probable transfer status 90 00:04:02,771 --> 00:04:06,177 I set it. 91 00:04:06,273 --> 00:04:09,533 and put it at the back of the queue. 92 00:04:10,326 --> 00:04:13,591 I solve the problem 93 00:04:13,655 --> 00:04:16,606 from top to down. 94 00:04:17,738 --> 00:04:21,557 We come back to the problem of Farmer Crossing River. 95 00:04:22,605 --> 00:04:25,690 To describe the problem 96 00:04:25,779 --> 00:04:29,100 is to set up the status. 97 00:04:29,180 --> 00:04:30,360 Then we know 98 00:04:30,446 --> 00:04:34,455 our problem is from 0000 to 1111. 99 00:04:34,549 --> 00:04:36,467 such a solving problem. 100 00:04:36,562 --> 00:04:38,885 The description of our data 101 00:04:38,979 --> 00:04:40,415 is very straight-forward. 102 00:04:40,495 --> 00:04:42,869 I use a bit vector to express 103 00:04:42,941 --> 00:04:45,857 all possible status. 104 00:04:45,931 --> 00:04:48,450 the 0 and 1 in the vector 105 00:04:48,530 --> 00:04:52,192 represents start side and another. 106 00:04:52,265 --> 00:04:54,979 Then the four thing 107 00:04:55,051 --> 00:04:58,441 has its fixed position. 108 00:04:58,521 --> 00:05:00,785 The vector 109 00:05:00,872 --> 00:05:01,846 has four bits. 110 00:05:01,934 --> 00:05:04,672 The value 111 00:05:04,755 --> 00:05:07,202 has 16 possibilities in total. 112 00:05:07,296 --> 00:05:10,970 But some is illegal. 113 00:05:11,058 --> 00:05:14,261 We get rid of such illegal status. 114 00:05:14,341 --> 00:05:17,169 to find ten legal status. 115 00:05:18,370 --> 00:05:19,716 We can save the bit vector 116 00:05:19,796 --> 00:05:22,536 in an integer. 117 00:05:22,632 --> 00:05:26,135 because the integer can do bit operation. 118 00:05:26,223 --> 00:05:30,007 For example, the status of the farmer at the other side 119 00:05:30,087 --> 00:05:31,971 and others at the start side 120 00:05:32,051 --> 00:05:33,292 is 121 00:05:33,381 --> 00:05:35,282 1000 122 00:05:35,376 --> 00:05:37,784 Of course, this is illegal. 123 00:05:37,863 --> 00:05:38,905 Because without him, 124 00:05:39,563 --> 00:05:41,552 wolf and sheep, sheep and vegetable 125 00:05:41,646 --> 00:05:42,729 has a conflict. 126 00:05:43,734 --> 00:05:46,721 The target side is expressed as 1111. 127 00:05:46,817 --> 00:05:49,080 After this 128 00:05:49,168 --> 00:05:53,991 I can describe the whole solving process 129 00:05:54,070 --> 00:05:56,425 the transfer of status. 130 00:05:57,671 --> 00:05:59,515 Another important issue, 131 00:05:59,595 --> 00:06:03,811 for such a bot vector 132 00:06:04,296 --> 00:06:08,549 how do I judge a specific thing 133 00:06:08,645 --> 00:06:11,414 is at this side or another. 134 00:06:11,790 --> 00:06:15,729 We will do some bit operation. 135 00:06:15,801 --> 00:06:17,801 For example, for the farmer, 136 00:06:17,881 --> 00:06:21,908 he is in the highest bit. 137 00:06:22,429 --> 00:06:27,270 We use 1000 138 00:06:27,390 --> 00:06:30,396 with the bit vector of status 139 00:06:30,484 --> 00:06:33,506 to do an And operation. 140 00:06:33,594 --> 00:06:37,762 If the farmer is at the target side. 141 00:06:37,851 --> 00:06:39,280 Its corresponding bit 142 00:06:39,383 --> 00:06:40,454 will be 1. 143 00:06:40,542 --> 00:06:41,692 the result of And operation 144 00:06:41,788 --> 00:06:43,294 must not be zero 145 00:06:43,384 --> 00:06:45,137 then returns true. 146 00:06:45,230 --> 00:06:49,061 If the bit of farmer is 0, 147 00:06:49,141 --> 00:06:50,873 which means he is at the start side. 148 00:06:50,968 --> 00:06:53,150 Then the result of And operation 149 00:06:53,222 --> 00:06:55,038 with 1000 150 00:06:55,102 --> 00:06:57,642 because the 100's 151 00:06:57,730 --> 00:07:00,808 first to third position is all 0 152 00:07:00,900 --> 00:07:03,051 the result must also be 0. 153 00:07:03,123 --> 00:07:05,156 So if the bit of farmer is also 0, 154 00:07:05,236 --> 00:07:07,708 the result of And is entirely 0. 155 00:07:07,789 --> 00:07:09,547 Then we can judge 156 00:07:09,631 --> 00:07:11,571 that the farmer is at the start side. 157 00:07:12,250 --> 00:07:14,927 It is the same as the other things. 158 00:07:15,015 --> 00:07:19,065 We use such a feature of the corresponding bit 159 00:07:19,137 --> 00:07:21,841 with the current status 160 00:07:21,929 --> 00:07:23,864 to do an And operation. 161 00:07:25,557 --> 00:07:27,153 Besides, we should also make sure 162 00:07:27,249 --> 00:07:30,323 whether the status is safe. 163 00:07:30,394 --> 00:07:33,290 If sheep and vegetable 164 00:07:33,370 --> 00:07:34,982 are at the same side 165 00:07:35,070 --> 00:07:38,119 and the farmer is not at this side, 166 00:07:38,202 --> 00:07:40,899 this is not safe and returns false. 167 00:07:41,609 --> 00:07:45,114 If sheep and wolf are at the same side 168 00:07:45,199 --> 00:07:48,266 and the farmer is not at this side, 169 00:07:48,854 --> 00:07:50,127 it also returns false. 170 00:07:50,214 --> 00:07:52,892 Other status return true. 171 00:07:54,843 --> 00:07:57,512 Let us clear up 172 00:07:57,616 --> 00:07:58,830 the requirement of this algorithm. 173 00:07:58,918 --> 00:08:01,979 We start with 174 00:08:02,068 --> 00:08:04,464 the status of 0000 175 00:08:04,560 --> 00:08:09,316 to the end status of 1111. 176 00:08:09,404 --> 00:08:12,614 In the sequence of the solution, 177 00:08:13,134 --> 00:08:15,529 there can not be duplicate status. 178 00:08:15,624 --> 00:08:17,202 Because duplicate is meaningless. 179 00:08:17,307 --> 00:08:18,674 After duplication, 180 00:08:18,756 --> 00:08:19,953 the next segment 181 00:08:20,047 --> 00:08:21,303 can have another round. 182 00:08:21,866 --> 00:08:24,078 It's only useless operation. 183 00:08:24,177 --> 00:08:27,222 If you can not control 184 00:08:27,301 --> 00:08:28,569 duplication well, 185 00:08:29,225 --> 00:08:30,388 it is probable that 186 00:08:30,476 --> 00:08:32,395 the algorithm will fall into dead cycle. 187 00:08:34,079 --> 00:08:36,045 The transfer process of the status 188 00:08:36,133 --> 00:08:39,687 are all in the way the farmer takes a thing 189 00:08:39,782 --> 00:08:43,066 from a side to another. 190 00:08:43,152 --> 00:08:45,685 Or he goes alone. 191 00:08:46,402 --> 00:08:49,172 We also use some auxiliary data structure 192 00:08:49,277 --> 00:08:54,022 to help farmer realize the transport process. 193 00:08:54,117 --> 00:08:57,033 The most important is queue. 194 00:08:57,145 --> 00:09:01,067 The queue needs to save the space status 195 00:09:01,154 --> 00:09:02,464 of current search. 196 00:09:03,751 --> 00:09:05,189 We also need to define 197 00:09:05,741 --> 00:09:08,986 the path that we have visited. 198 00:09:10,480 --> 00:09:11,877 To define the path, 199 00:09:11,941 --> 00:09:14,309 we mainly record 200 00:09:14,405 --> 00:09:15,589 whether the status 201 00:09:15,677 --> 00:09:17,650 has been visited. 202 00:09:17,724 --> 00:09:20,031 If not, 203 00:09:20,675 --> 00:09:22,535 we can go into this status. 204 00:09:23,109 --> 00:09:27,042 Meantime, we can set the precursor of this status 205 00:09:27,137 --> 00:09:30,761 as the previous one just now. 206 00:09:31,523 --> 00:09:33,439 To record the path of the status, 207 00:09:33,491 --> 00:09:34,648 the variable 208 00:09:34,752 --> 00:09:36,688 is an array. 209 00:09:36,784 --> 00:09:38,192 The array 210 00:09:38,288 --> 00:09:41,386 is corresponding to the 16 211 00:09:41,867 --> 00:09:43,279 possible status. 212 00:09:44,104 --> 00:09:46,562 We set the initial value as -1. 213 00:09:46,666 --> 00:09:49,402 The value of it, 214 00:09:49,482 --> 00:09:51,215 is in the process of search 215 00:09:51,311 --> 00:09:53,557 from the previous status 216 00:09:53,653 --> 00:09:55,081 to the current one. 217 00:09:55,647 --> 00:09:56,943 The precursor of it 218 00:09:57,038 --> 00:09:58,632 is what we record 219 00:10:00,870 --> 00:10:01,910 As for implementation of the algorithm, 220 00:10:01,998 --> 00:10:05,119 we first define some variables. 221 00:10:05,211 --> 00:10:08,996 And set the array for path 222 00:10:09,572 --> 00:10:11,700 as -1. 223 00:10:12,268 --> 00:10:15,542 That is, all such status 224 00:10:15,630 --> 00:10:17,222 have not been visited. 225 00:10:17,310 --> 00:10:20,808 Then we can set the start status as 226 00:10:20,896 --> 00:10:21,889 0000 227 00:10:22,457 --> 00:10:24,235 and push it into queue. 228 00:10:25,132 --> 00:10:28,236 Meantime, we set the 0 position 229 00:10:28,324 --> 00:10:30,615 corresponding to the start status 230 00:10:30,692 --> 00:10:32,993 We set its precursor as 0. 231 00:10:33,065 --> 00:10:36,800 It mainly differs from the -1 status 232 00:10:36,881 --> 00:10:38,377 that it has not been visited. 233 00:10:39,258 --> 00:10:43,068 Let us look at the main frame. 234 00:10:44,268 --> 00:10:46,248 Now, the head of the queue 235 00:10:46,342 --> 00:10:51,183 is the start node of the entire space. 236 00:10:51,270 --> 00:10:52,660 That is, 0000. 237 00:10:53,496 --> 00:10:54,820 Then we enter into a cycle. 238 00:10:55,704 --> 00:10:57,781 When the queue is not empty 239 00:10:57,864 --> 00:11:03,234 and the goal status has not appeared. 240 00:11:03,947 --> 00:11:05,794 We pop a node 241 00:11:06,242 --> 00:11:09,287 from the head of the queue. 242 00:11:09,671 --> 00:11:14,519 Then we try to take one of these things 243 00:11:14,606 --> 00:11:16,200 or nothing. 244 00:11:16,578 --> 00:11:18,932 We let the variable mover 245 00:11:19,320 --> 00:11:22,196 change from 1 246 00:11:22,597 --> 00:11:27,389 We have a try of the choice below 247 00:11:27,910 --> 00:11:29,215 which is 248 00:11:29,317 --> 00:11:33,983 1 2 4 8 249 00:11:34,863 --> 00:11:39,820 corresponding to the start variable 0001 250 00:11:41,132 --> 00:11:42,399 move left by a bit 251 00:11:42,495 --> 00:11:44,199 into 0010 252 00:11:44,635 --> 00:11:45,671 by another bit 253 00:11:45,767 --> 00:11:48,103 into 0100 254 00:11:48,737 --> 00:11:50,295 by the last bit 255 00:11:50,375 --> 00:11:52,636 into 1000 256 00:11:53,180 --> 00:12:00,765 corresponding to sheep, vegetable and wolf man. 257 00:12:00,869 --> 00:12:03,887 For the feature bit of these things, 258 00:12:04,349 --> 00:12:07,595 the previous three is the farmer taking some things 259 00:12:08,403 --> 00:12:10,048 the last 1000 260 00:12:10,120 --> 00:12:11,342 is that the farmer takes nothing. 261 00:12:11,423 --> 00:12:13,045 He rows the empty boat 262 00:12:14,272 --> 00:12:15,856 from a side to another. 263 00:12:16,646 --> 00:12:20,060 In each cycle, 264 00:12:20,141 --> 00:12:22,431 we first make sure 265 00:12:22,887 --> 00:12:28,330 whether the farmer and the thing he is going to take 266 00:12:28,418 --> 00:12:32,121 are at the same side. 267 00:12:33,633 --> 00:12:37,984 For example, the start status 268 00:12:38,072 --> 00:12:39,191 0000 269 00:12:40,277 --> 00:12:44,089 the farmer wants to take sheep 270 00:12:45,182 --> 00:12:48,872 You see, the feature bits of farmer 271 00:12:49,432 --> 00:12:52,581 and sheep 272 00:12:53,062 --> 00:12:55,253 are equal 273 00:12:55,628 --> 00:12:58,353 so he can take it. 274 00:12:58,784 --> 00:12:59,652 Then 275 00:12:59,748 --> 00:13:04,330 we go into another status. 276 00:13:05,340 --> 00:13:11,281 we have an Or operation 277 00:13:11,740 --> 00:13:16,843 of the feature bits of farmer 278 00:13:17,219 --> 00:13:19,388 and the thing he takes. 279 00:13:21,216 --> 00:13:26,100 And I get a new vector. 280 00:13:26,614 --> 00:13:28,110 This vector 281 00:13:28,742 --> 00:13:33,212 does an XOR operation 282 00:13:34,122 --> 00:13:39,097 with the status ahead 283 00:13:39,737 --> 00:13:44,153 the status just now is 0000 284 00:13:44,617 --> 00:13:46,805 the XOR operation 285 00:13:46,885 --> 00:13:49,215 bit by bit 286 00:13:50,638 --> 00:13:54,653 is that the farmer and the thing he takes 287 00:13:55,180 --> 00:13:57,953 change 288 00:13:58,601 --> 00:13:59,609 from 0 289 00:13:59,698 --> 00:14:03,377 to 1 290 00:14:04,853 --> 00:14:07,796 If it is originally 1 291 00:14:07,876 --> 00:14:09,070 it becomes 0 292 00:14:09,159 --> 00:14:10,676 Another two things 293 00:14:10,764 --> 00:14:13,094 will not change. 294 00:14:13,171 --> 00:14:14,632 That is, 295 00:14:14,720 --> 00:14:20,713 we change from an old status 296 00:14:22,483 --> 00:14:25,104 into 297 00:14:25,781 --> 00:14:27,529 a new one 298 00:14:27,960 --> 00:14:33,306 Then we consider whether the new status 299 00:14:33,378 --> 00:14:35,389 is safe. 300 00:14:36,951 --> 00:14:40,200 And let us see whether the new status 301 00:14:40,788 --> 00:14:43,736 its path 302 00:14:43,817 --> 00:14:46,579 has been visited. 303 00:14:46,651 --> 00:14:48,489 That is, whether this status 304 00:14:48,561 --> 00:14:52,937 is in the path of 305 00:14:53,017 --> 00:14:53,896 a solution 306 00:14:53,974 --> 00:14:55,065 If not, 307 00:14:55,481 --> 00:15:01,338 I can accept 308 00:15:01,410 --> 00:15:02,354 this new status. 309 00:15:02,434 --> 00:15:04,842 We record it into 310 00:15:04,938 --> 00:15:07,519 a temporary array 311 00:15:07,969 --> 00:15:09,166 of the path. 312 00:15:09,254 --> 00:15:11,222 And its precursor 313 00:15:11,310 --> 00:15:14,830 is set as the status just now. 314 00:15:16,342 --> 00:15:21,019 And put the new status 315 00:15:21,115 --> 00:15:22,985 into the queue. 316 00:15:25,016 --> 00:15:26,612 To extend 317 00:15:26,700 --> 00:15:30,196 for width-first search afterwards 318 00:15:31,090 --> 00:15:32,917 The main framework is 319 00:15:32,981 --> 00:15:36,090 that we continue to 320 00:15:36,721 --> 00:15:40,399 pop the node 321 00:15:41,457 --> 00:15:42,785 of the queue 322 00:15:43,210 --> 00:15:45,502 and do corresponding operations 323 00:15:47,681 --> 00:15:49,970 until the queue is empty 324 00:15:51,479 --> 00:15:54,463 or the target status 325 00:15:54,543 --> 00:15:56,447 appears 326 00:15:57,843 --> 00:16:01,205 If this problem can get a solution 327 00:16:01,285 --> 00:16:03,952 we take route[15] 328 00:16:04,016 --> 00:16:06,224 such a precursor 329 00:16:06,295 --> 00:16:10,531 and find its precursor one after one 330 00:16:10,611 --> 00:16:13,968 until route0 331 00:16:14,072 --> 00:16:18,436 Then we get an inverted sequence of a solution 332 00:16:18,516 --> 00:16:20,846 if we reverse this sequence 333 00:16:20,917 --> 00:16:22,773 it is a correct solution. 334 00:16:23,341 --> 00:16:25,919 If until finished 335 00:16:26,007 --> 00:16:27,965 the main algorithm framework just now 336 00:16:28,037 --> 00:16:31,912 has not got a reasonable solution of route[15] 337 00:16:32,609 --> 00:16:33,522 at this time 338 00:16:33,618 --> 00:16:36,521 we can not solve this problem 339 00:16:36,978 --> 00:16:38,134 then return failure. 340 00:16:38,662 --> 00:16:40,625 Let us observe 341 00:16:40,689 --> 00:16:44,944 the solving process of this algorithm. 342 00:16:45,032 --> 00:16:48,899 In fact, from the start status 343 00:16:48,980 --> 00:16:50,896 when we try to extend it 344 00:16:50,966 --> 00:16:55,125 only to find 345 00:16:55,193 --> 00:16:56,778 there is only one choice 346 00:16:56,859 --> 00:16:58,269 the other two 347 00:16:58,349 --> 00:16:59,496 is conflicting. 348 00:16:59,584 --> 00:17:01,181 From the start status 349 00:17:01,245 --> 00:17:02,876 to the next status 350 00:17:03,589 --> 00:17:05,729 we choose sheep 351 00:17:05,785 --> 00:17:09,323 that is, there are two bits 352 00:17:09,392 --> 00:17:10,603 changed 353 00:17:10,675 --> 00:17:13,274 the two left do not change. 354 00:17:13,353 --> 00:17:16,156 then we change into the next status. 355 00:17:16,250 --> 00:17:18,153 only the farmer change 356 00:17:18,249 --> 00:17:20,405 others do not. 357 00:17:20,477 --> 00:17:23,122 We from top to down 358 00:17:23,186 --> 00:17:26,476 save such reasonabl status 359 00:17:27,259 --> 00:17:29,608 into our queue layer by layer. 360 00:17:29,680 --> 00:17:31,503 And wait for the extend of the next layer 361 00:17:31,598 --> 00:17:32,639 At last, 362 00:17:32,735 --> 00:17:35,514 we meet the solution status. 363 00:17:35,599 --> 00:17:38,474 the process of solution complete. 364 00:17:40,296 --> 00:17:42,746 At last, a little game is give to you. 365 00:17:43,455 --> 00:17:46,097 on a dark night, 366 00:17:46,169 --> 00:17:49,415 there is a family of five carrying a lamp 367 00:17:49,511 --> 00:17:51,101 across a single log 368 00:17:51,176 --> 00:17:52,682 The five 369 00:17:52,777 --> 00:17:55,075 cross at different speeds. 370 00:17:55,145 --> 00:17:59,068 And only two is allowed 371 00:17:59,141 --> 00:18:01,286 to cross the log at the same time 372 00:18:01,363 --> 00:18:02,534 to the other side. 373 00:18:02,601 --> 00:18:05,327 and take the lamp back 374 00:18:05,399 --> 00:18:07,881 to take people this side 375 00:18:07,969 --> 00:18:10,869 the duration of the lamp 376 00:18:10,957 --> 00:18:12,060 is pretty short 377 00:18:12,132 --> 00:18:14,445 how do we design a scheme 378 00:18:14,531 --> 00:18:18,190 for the five to cross the log. 379 00:18:18,853 --> 00:18:19,614 Thank you.