1
00:00:00,000 --> 00:00:13,070

2
00:00:13,070 --> 00:00:13,715
>> ROB Bowden: Hi.

3
00:00:13,715 --> 00:00:17,800
Tôi Rob, và tôi hy vọng của bạn
trò chơi cho trò chơi của 15.

4
00:00:17,800 --> 00:00:22,040
Bây giờ, có bốn chức năng bạn cần
để thực hiện trong chương trình này - init,

5
00:00:22,040 --> 00:00:24,650
vẽ, di chuyển, và chiến thắng.

6
00:00:24,650 --> 00:00:27,230
Vì vậy, chúng ta hãy nhìn vào init.

7
00:00:27,230 --> 00:00:32,930
>> Ở đây, chúng ta thấy điều đầu tiên chúng tôi
sẽ làm là khai báo một biến

8
00:00:32,930 --> 00:00:34,600
được gọi là truy cập.

9
00:00:34,600 --> 00:00:37,620
Nó sẽ được khởi tạo
d lần d trừ đi 1.

10
00:00:37,620 --> 00:00:40,200
Hãy nhớ rằng d là kích thước
hội đồng quản trị của chúng tôi.

11
00:00:40,200 --> 00:00:43,840
Làm thế nào init là sẽ làm việc là nó sẽ
để lặp lại trên toàn bộ hội đồng quản trị

12
00:00:43,840 --> 00:00:46,050
và chúng ta sẽ bắt đầu
ở phía trên bên trái.

13
00:00:46,050 --> 00:00:48,570
>> Và chúng ta hãy chỉ nói rằng chúng ta
có 4 4 hội đồng quản trị.

14
00:00:48,570 --> 00:00:51,220
Vì vậy, phía trên bên trái chúng tôi
sẽ nói là 15.

15
00:00:51,220 --> 00:00:53,960
Và sau đó chúng tôi chỉ sẽ đếm
thông qua các hội đồng, nói rằng 15, 14, 13,

16
00:00:53,960 --> 00:00:58,510
12, 11, 10, 9, 8, 7,
6, 5, 4, và như vậy.

17
00:00:58,510 --> 00:01:03,780
Vì vậy, phía trên bên trái, chúng tôi hy vọng sẽ được d lần
d trừ đi 1, mà trong 4 của 4

18
00:01:03,780 --> 00:01:08,290
trường hợp là có được 16 trừ đi
1, đó là chính xác 15.

19
00:01:08,290 --> 00:01:10,885
>> Và bây giờ đây là nơi mà chúng ta sẽ
duyệt qua toàn bộ hội đồng quản trị.

20
00:01:10,885 --> 00:01:14,720
Và chúng ta sẽ thiết lập mỗi vị trí trong
hội đồng quản trị với giá trị hiện tại của

21
00:01:14,720 --> 00:01:19,090
truy cập của chúng tôi, và sau đó truy cập sẽ
để làm giảm giá trị, do đó tiếp theo

22
00:01:19,090 --> 00:01:22,300
vị trí chúng ta đạt được là sẽ có
truy cập là một trong ít hơn

23
00:01:22,300 --> 00:01:23,690
vị trí trước đó.

24
00:01:23,690 --> 00:01:26,970
Vì vậy, chúng tôi bước đầu đã có 15
giảm giá trị truy cập.

25
00:01:26,970 --> 00:01:30,065
Vì vậy, sau đó chúng ta sẽ chỉ định 14 cho
vị trí tiếp theo, lượng giảm truy cập,

26
00:01:30,065 --> 00:01:33,710
và chúng ta sẽ được giao
13, và như vậy.

27
00:01:33,710 --> 00:01:37,620
>> Cuối cùng, chúng ta cần phải xử lý góc
Trường hợp, nếu hội đồng quản trị có một thậm chí

28
00:01:37,620 --> 00:01:44,450
kích thước, sau đó chỉ cần làm 15, 14, 13,
12, tất cả các con đường xuống 3, 2, 1, là

29
00:01:44,450 --> 00:01:46,780
sẽ để lại cho chúng tôi
một hội đồng quản trị giải quyết được.

30
00:01:46,780 --> 00:01:49,390
Và chúng ta phải trao đổi 1 và 2.

31
00:01:49,390 --> 00:01:52,930
Vì vậy, nếu d mod 2 bằng 0, đó là
làm thế nào chúng ta sẽ kiểm tra

32
00:01:52,930 --> 00:01:54,410
để xem nếu nó thậm chí còn.

33
00:01:54,410 --> 00:01:59,810
Nếu d mod 2 bằng 0, sau đó trong hàng d trừ
1, đó là hàng dưới cùng, và

34
00:01:59,810 --> 00:02:05,430
vị trí d trừ 2, hoặc cột d trừ
2, chúng ta sẽ thiết lập đó để 2, và

35
00:02:05,430 --> 00:02:07,860
cột d trừ 3 chúng tôi
sẽ thiết lập để 1.

36
00:02:07,860 --> 00:02:12,170
Vì vậy, đó chỉ là đảo ngược nơi
1 và 2 hiện đang có.

37
00:02:12,170 --> 00:02:16,270
>> Cuối cùng, chúng ta sẽ thiết lập rất
dưới cùng bên phải bằng trống, nơi

38
00:02:16,270 --> 00:02:20,700
trống đã được định nghĩa băm
ở đầu là 0.

39
00:02:20,700 --> 00:02:26,785
Vì vậy, đó không phải là thực sự cần thiết,
vì điều này cho vòng lặp là sẽ có

40
00:02:26,785 --> 00:02:30,610
thiết lập các góc dưới bên phải để 0, vì
truy cập sẽ tự nhiên đạt 0.

41
00:02:30,610 --> 00:02:34,610
Nhưng điều đó phụ thuộc vào chúng tôi biết rằng
trống được băm để tìm một 0.

42
00:02:34,610 --> 00:02:38,280
Nếu tôi đi vào chương trình này và sau đó
thay đổi trống ở đầu trang 100, nó

43
00:02:38,280 --> 00:02:39,770
vẫn phải làm việc.

44
00:02:39,770 --> 00:02:43,180
>> Vì vậy, đây chỉ là đảm bảo rằng các
phía dưới bên phải là thực sự bằng của chúng tôi

45
00:02:43,180 --> 00:02:44,870
giá trị trống.

46
00:02:44,870 --> 00:02:50,270
Cuối cùng, chúng tôi có hai biến toàn cầu,
để trống tôi và trống j, và chúng ta thấy

47
00:02:50,270 --> 00:02:53,360
những tuyên bố ở đầu trang.

48
00:02:53,360 --> 00:02:56,270
Và chúng ta sẽ sử dụng hai toàn cầu
biến để theo dõi các

49
00:02:56,270 --> 00:02:59,040
vị trí của trống, vì vậy mà chúng ta không
cần phải xem xét thông qua toàn bộ

50
00:02:59,040 --> 00:03:03,890
hội đồng quản trị để tìm chỗ trống mỗi đơn
Hiện chúng tôi cố gắng để thực hiện một di chuyển.

51
00:03:03,890 --> 00:03:08,450
Vì vậy, vị trí của trống luôn luôn là
sẽ bắt đầu ở góc dưới bên phải.

52
00:03:08,450 --> 00:03:13,270
Vì vậy, phía dưới bên phải được cho bởi
chỉ số d trừ đi 1, d trừ đi 1.

53
00:03:13,270 --> 00:03:14,880
Vì vậy, đó là init.

54
00:03:14,880 --> 00:03:17,040
>> Bây giờ chúng ta chuyển sang vẽ.

55
00:03:17,040 --> 00:03:19,370
Vì vậy, hòa là có được tương tự
nơi chúng ta sẽ lặp

56
00:03:19,370 --> 00:03:20,970
trên toàn bộ hội đồng quản trị.

57
00:03:20,970 --> 00:03:25,400
Và chúng tôi chỉ muốn in giá trị
đó là trong mỗi vị trí của hội đồng quản trị.

58
00:03:25,400 --> 00:03:29,580
Vì vậy, ở đây, chúng tôi đang in giá trị đó là
ở mỗi vị trí của hội đồng quản trị.

59
00:03:29,580 --> 00:03:32,280
Và nhận thấy rằng chúng tôi đang làm -.

60
00:03:32,280 --> 00:03:37,410
Và đó chỉ là nói printf mà
không phân biệt nếu đó là một chữ số hoặc

61
00:03:37,410 --> 00:03:42,010
hai chữ số, chúng tôi vẫn muốn nó
mất hai cột trong in ra,

62
00:03:42,010 --> 00:03:46,290
do đó nếu chúng ta có hai chữ số và một
số chữ số trong cùng một bảng, chúng tôi

63
00:03:46,290 --> 00:03:49,450
hội đồng quản trị sẽ vẫn nhìn đẹp và vuông.

64
00:03:49,450 --> 00:03:54,190
>> Vì vậy, chúng tôi muốn làm điều đó cho tất cả các giá trị
trong hội đồng quản trị, ngoại trừ trống.

65
00:03:54,190 --> 00:03:58,260
Vì vậy, nếu các vị trí trong hội đồng quản trị bằng
trống, sau đó chúng tôi đặc biệt

66
00:03:58,260 --> 00:04:01,730
muốn in ra chỉ là một gạch dưới
để đại diện cho trống, thay vì

67
00:04:01,730 --> 00:04:05,150
bất cứ điều gì giá trị của
trống thực sự.

68
00:04:05,150 --> 00:04:08,500
>> Cuối cùng, chúng tôi muốn in
ra một dòng mới.

69
00:04:08,500 --> 00:04:11,970
Chú ý rằng điều này vẫn còn bên trong
bên ngoài vòng lặp, nhưng bên ngoài

70
00:04:11,970 --> 00:04:13,200
bên trong vòng lặp.

71
00:04:13,200 --> 00:04:17,930
Từ bên ngoài này cho vòng lặp được lặp lại
trên tất cả các hàng, và do đó đây là printf

72
00:04:17,930 --> 00:04:22,130
sẽ chỉ in một dòng mới, vì vậy chúng tôi
di chuyển trên để in ra các hàng tiếp theo.

73
00:04:22,130 --> 00:04:23,910
Và đó là nó cho hòa.

74
00:04:23,910 --> 00:04:27,770
>> Vì vậy, bây giờ chúng ta hãy chuyển để di chuyển.

75
00:04:27,770 --> 00:04:32,590
Bây giờ, chúng tôi vượt qua di chuyển, ngói rằng
người sử dụng được nhập vào trò chơi - họ

76
00:04:32,590 --> 00:04:36,360
nhập ngói họ muốn di chuyển - và
bạn đang nghĩ để trả về một bool, vì vậy

77
00:04:36,360 --> 00:04:39,300
đúng hoặc sai, tùy thuộc vào
cho dù di chuyển đã được thực sự

78
00:04:39,300 --> 00:04:43,360
hợp lệ - cho dù ngói có thể được
di chuyển vào không gian trống.

79
00:04:43,360 --> 00:04:48,340
>> Vì vậy, ở đây, chúng ta khai báo một biến địa phương,
tile_1 và tile_j, mà sẽ

80
00:04:48,340 --> 00:04:52,150
tương tự như blank_i và blank_j,
ngoại trừ nó sẽ theo dõi các

81
00:04:52,150 --> 00:04:54,910
vị trí của ngói.

82
00:04:54,910 --> 00:05:00,370
Bây giờ đây, chúng ta sẽ sử dụng blank_i
và blank_j và nói tất cả rồi, vậy

83
00:05:00,370 --> 00:05:01,930
đây là trống trên bảng.

84
00:05:01,930 --> 00:05:04,420
>> Bây giờ, là ngói trên trống?

85
00:05:04,420 --> 00:05:06,210
Là ngói bên trái của trống?

86
00:05:06,210 --> 00:05:07,420
Là gạch để ở bên phải của trống?

87
00:05:07,420 --> 00:05:08,970
Là gạch dưới trống?

88
00:05:08,970 --> 00:05:13,330
Vì vậy, nếu gạch là trong bất kỳ của những
vị trí, sau đó chúng tôi biết rằng ngói

89
00:05:13,330 --> 00:05:16,390
có thể được di chuyển vào vị trí trống và
trống có thể được di chuyển đến nơi

90
00:05:16,390 --> 00:05:18,240
ngói hiện nay.

91
00:05:18,240 --> 00:05:26,400
>> Vì vậy, ở đây, chúng ta nói nếu hội đồng quản trị ở vị trí
blank_i trừ 1 blank_j.

92
00:05:26,400 --> 00:05:31,120
Vì vậy, đây được nói là ngói
trên các trống hiện tại?

93
00:05:31,120 --> 00:05:34,350
Và nếu như vậy, chúng ta sẽ nhớ
đó là vị trí của ngói.

94
00:05:34,350 --> 00:05:37,870
Gạch ở vị trí blank_i
trừ đi 1 và blank_j.

95
00:05:37,870 --> 00:05:40,660
bây giờ đầu tiên, chúng tôi cũng có kiểm tra này
ngay tại đây, vì vậy blank_i là

96
00:05:40,660 --> 00:05:41,760
lớn hơn 0.

97
00:05:41,760 --> 00:05:43,410
>> Tại sao chúng ta muốn làm điều đó?

98
00:05:43,410 --> 00:05:47,290
Vâng, nếu trống là ở hàng đầu
Hội đồng quản trị, sau đó chúng tôi không muốn

99
00:05:47,290 --> 00:05:51,240
tìm trên trống cho ngói từ
không có gì ở trên đầu là

100
00:05:51,240 --> 00:05:52,430
hàng của bảng.

101
00:05:52,430 --> 00:05:55,950
Đây là cách bạn có thể kết thúc nhận
một cái gì đó giống như một lỗi phân khúc hay

102
00:05:55,950 --> 00:05:59,030
chương trình của bạn chỉ có thể làm việc
theo những cách bất ngờ.

103
00:05:59,030 --> 00:06:04,310
Vì vậy, đây là đảm bảo rằng chúng tôi không
tìm ở những nơi mà không phải là hợp lệ.

104
00:06:04,310 --> 00:06:08,470
>> Bây giờ chúng ta sẽ làm điều tương tự cho
tất cả các kết hợp có thể khác.

105
00:06:08,470 --> 00:06:13,250
Vì vậy, ở đây, chúng tôi đang tìm kiếm dưới trống
để xem nếu đó là ngói.

106
00:06:13,250 --> 00:06:16,950
Và chúng tôi cũng phải chắc chắn chúng tôi
không trên hàng dưới cùng, nếu không chúng ta

107
00:06:16,950 --> 00:06:18,910
không nên tìm kiếm ngói.

108
00:06:18,910 --> 00:06:25,040
Ở đây, chúng ta sẽ xem xét bên trái của
trống để xem nếu nó là ngói.

109
00:06:25,040 --> 00:06:27,860
Và chúng ta không nên nhìn sang bên trái
nếu chúng ta đang ở trong cột ngoài cùng bên trái.

110
00:06:27,860 --> 00:06:30,100
Và ở đây chúng ta sẽ nhìn vào
bên phải của trống, và chúng ta không nên

111
00:06:30,100 --> 00:06:33,340
nhìn bên phải nếu chúng ta
trong cột bên phải.

112
00:06:33,340 --> 00:06:37,820
>> Vì vậy, nếu không có những điều đó là đúng,
điều đó có nghĩa ngói không liền kề

113
00:06:37,820 --> 00:06:39,640
để trống và chúng tôi có thể trả về false.

114
00:06:39,640 --> 00:06:41,230
Động thái này là không hợp lệ.

115
00:06:41,230 --> 00:06:47,010
Nhưng, nếu một trong những người là đúng, sau đó tại
thời điểm này, chúng ta biết rằng tile_i và

116
00:06:47,010 --> 00:06:50,540
tile_j bằng với
vị trí của ngói.

117
00:06:50,540 --> 00:06:55,210
Và như vậy, chúng ta có thể cập nhật các bảng tại
vị trí tile_i và tile_j.

118
00:06:55,210 --> 00:06:59,820
Chúng ta biết được giá trị mới sẽ là trống
và rằng blank_i vị trí

119
00:06:59,820 --> 00:07:02,950
blank_j, đó là bản gốc
trống - chúng ta biết ngói sẽ

120
00:07:02,950 --> 00:07:04,030
di chuyển ở đó.

121
00:07:04,030 --> 00:07:07,610
>> Chú ý chúng ta không thực sự phải làm một
trao đổi thực sự ở đây, kể từ khi chúng ta biết được

122
00:07:07,610 --> 00:07:09,850
giá trị mà cần phải được chèn
vào những vị trí.

123
00:07:09,850 --> 00:07:13,780
Chúng ta không cần một tạm thời
biến xung quanh.

124
00:07:13,780 --> 00:07:16,920
>> Cuối cùng, chúng ta cần nhớ rằng chúng tôi
có biến toàn cầu của chúng tôi là

125
00:07:16,920 --> 00:07:18,980
theo dõi các vị trí
của trống.

126
00:07:18,980 --> 00:07:22,780
Vì vậy, chúng tôi muốn để cập nhật vị trí của
trống là nơi ngói

127
00:07:22,780 --> 00:07:24,190
ban đầu là.

128
00:07:24,190 --> 00:07:27,680
Cuối cùng, chúng tôi trở lại đúng từ
di chuyển đã thành công.

129
00:07:27,680 --> 00:07:31,110
Chúng tôi trao đổi thành công
trống với ngói.

130
00:07:31,110 --> 00:07:34,890
>> Được rồi, chúng ta nên cuối cùng
cần phải kiểm tra won.

131
00:07:34,890 --> 00:07:39,900
Vì vậy, chiến thắng tương tự trả về một bool nơi
đúng là sẽ chỉ ra rằng

132
00:07:39,900 --> 00:07:41,460
người sử dụng đã thắng.

133
00:07:41,460 --> 00:07:43,780
Và sai được chỉ ra rằng
các trò chơi vẫn còn đang.

134
00:07:43,780 --> 00:07:46,340
Người sử dụng đã không giành chiến thắng.

135
00:07:46,340 --> 00:07:52,100
Vì vậy, điều này là có được khá nhiều
đối diện của init, init nơi,

136
00:07:52,100 --> 00:07:56,920
nhớ, chúng ta khởi tạo hội đồng quản trị
15, 14, 13, 12, vv.

137
00:07:56,920 --> 00:08:03,000
Trong khi đó, chiến thắng, chúng tôi muốn kiểm tra xem
hội đồng quản trị là 1, 2, 3, 4, 5, và như vậy.

138
00:08:03,000 --> 00:08:06,600
>> Vì vậy, chúng ta sẽ khởi tạo của chúng tôi
chống tới 1 vì đó là những gì hàng đầu

139
00:08:06,600 --> 00:08:08,400
bên trái của hội đồng quản trị nên được.

140
00:08:08,400 --> 00:08:10,860
Và sau đó chúng ta sẽ lặp
trên toàn bộ hội đồng quản trị.

141
00:08:10,860 --> 00:08:13,690
Hãy bỏ qua tình trạng này
trong một giây.

142
00:08:13,690 --> 00:08:18,410
Và tình trạng này là chỉ cần đi đến
kiểm tra là hội đồng quản trị tại vị trí này

143
00:08:18,410 --> 00:08:20,790
bằng với số lượng hiện tại?

144
00:08:20,790 --> 00:08:27,040
Nếu như vậy, tăng số lượng để các
vị trí tiếp theo chúng ta nhìn vào là một trong những cao

145
00:08:27,040 --> 00:08:29,690
hơn so với vị trí chúng tôi đang ở ngay bây giờ.

146
00:08:29,690 --> 00:08:32,700
>> Vì vậy, đó là cách chúng tôi nhận được
trên bên trái nên được 1.

147
00:08:32,700 --> 00:08:33,950
Tăng số lượng 2.

148
00:08:33,950 --> 00:08:35,010
Nhìn vào vị trí tiếp theo.

149
00:08:35,010 --> 00:08:35,690
Đây là 2?

150
00:08:35,690 --> 00:08:37,659
Nếu như vậy, thặng dư đếm đến 3.

151
00:08:37,659 --> 00:08:39,179
Vị trí tiếp theo là 3 này?

152
00:08:39,179 --> 00:08:42,440
Nếu như vậy, tăng số lượng
đến 4, và như vậy.

153
00:08:42,440 --> 00:08:49,190
Vì vậy, nếu có bất kỳ vị trí trên
hội đồng quản trị không bằng số của chúng tôi,

154
00:08:49,190 --> 00:08:52,640
sau đó chúng tôi muốn trở lại sai vì đó
có nghĩa là có một số gạch đó là

155
00:08:52,640 --> 00:08:55,490
không ở đúng vị trí.

156
00:08:55,490 --> 00:08:58,810
>> Vì vậy, ở đây, những gì là tình trạng này đang làm gì?

157
00:08:58,810 --> 00:09:02,170
Vâng, hãy nhớ rằng trống là
nghĩa vụ phải đi vào góc dưới bên phải.

158
00:09:02,170 --> 00:09:06,180
Và giá trị của trống có thể không
nhất thiết phải tương đương với giá trị của

159
00:09:06,180 --> 00:09:11,080
phản có nghĩa là sẽ đạt được
ở góc dưới bên phải.

160
00:09:11,080 --> 00:09:15,760
Vì vậy, chúng tôi đặc biệt muốn kiểm tra xem tôi
bằng bằng d trừ đi 1 và j bình đẳng

161
00:09:15,760 --> 00:09:19,470
d bằng trừ 1 - được nói rằng nếu chúng tôi
đang tìm kiếm ở góc dưới bên phải

162
00:09:19,470 --> 00:09:22,050
hội đồng quản trị - sau đó chúng tôi chỉ
muốn tiếp tục.

163
00:09:22,050 --> 00:09:26,200
Chúng tôi muốn bỏ qua đặc biệt này
lặp đi lặp lại của vòng lặp cho.

164
00:09:26,200 --> 00:09:31,250
>> Và như vậy, nếu chúng ta quản lý để có được thông qua này
lồng nhau cho vòng lặp, có nghĩa là

165
00:09:31,250 --> 00:09:34,690
không có gạch đó là trong
vị trí không chính xác.

166
00:09:34,690 --> 00:09:38,900
Và chúng tôi thoát ra khỏi vòng lặp và đến
ở đây, nơi chúng tôi có thể trở lại đúng sự thật.

167
00:09:38,900 --> 00:09:41,800
Tất cả các gạch là ở các vị trí chính xác
và điều đó có nghĩa người dùng có

168
00:09:41,800 --> 00:09:43,230
thắng.

169
00:09:43,230 --> 00:09:44,460
Và đó là nó.

170
00:09:44,460 --> 00:09:46,550
Tên tôi là Rob Bowden, và điều này là 15.

171
00:09:46,550 --> 00:09:52,726