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
Saya Rob, dan saya berharap anda
permainan untuk permainan 15.

4
00:00:17,800 --> 00:00:22,040
Sekarang, terdapat empat fungsi yang anda perlu
untuk melaksanakan program ini - init,

5
00:00:22,040 --> 00:00:24,650
menarik, bergerak, dan menang.

6
00:00:24,650 --> 00:00:27,230
Jadi, mari kita lihat init.

7
00:00:27,230 --> 00:00:32,930
>> Di sini, kita melihat perkara yang pertama kita
akan lakukan adalah mengisytiharkan pembolehubah

8
00:00:32,930 --> 00:00:34,600
dipanggil kaunter.

9
00:00:34,600 --> 00:00:37,620
Ia akan dimulakan
untuk d kali d tolak 1.

10
00:00:37,620 --> 00:00:40,200
Ingat bahawa d ialah dimensi
lembaga Pengarah kami.

11
00:00:40,200 --> 00:00:43,840
Bagaimana init akan bekerja adalah ia akan
untuk melelar atas seluruh lembaga

12
00:00:43,840 --> 00:00:46,050
dan kita akan memulakan
di sebelah kiri atas.

13
00:00:46,050 --> 00:00:48,570
>> Dan mari kita hanya mengatakan bahawa kita
mempunyai 4 oleh 4 kapal.

14
00:00:48,570 --> 00:00:51,220
Jadi sebelah kiri kami
akan katakan adalah 15.

15
00:00:51,220 --> 00:00:53,960
Dan kemudian kami hanya akan mengira
menerusi papan, mengatakan 15, 14, 13,

16
00:00:53,960 --> 00:00:58,510
12, 11, 10, 9, 8, 7,
6, 5, 4, dan sebagainya.

17
00:00:58,510 --> 00:01:03,780
Jadi sebelah kiri atas, kami menjangka akan d kali
d tolak 1, yang pada 4 oleh 4

18
00:01:03,780 --> 00:01:08,290
kes akan menjadi 16 tolak
1, iaitu dengan betul 15.

19
00:01:08,290 --> 00:01:10,885
>> Dan kini di sini di mana kita akan
melelar atas seluruh lembaga.

20
00:01:10,885 --> 00:01:14,720
Dan kita akan menetapkan setiap kedudukan dalam
lembaga untuk nilai semasa

21
00:01:14,720 --> 00:01:19,090
kaunter, dan kemudian kaunter akan
untuk SUSUTAN, supaya seterusnya

22
00:01:19,090 --> 00:01:22,300
kedudukan kita mencapai akan mempunyai
kaunter menjadi salah satu kurang daripada

23
00:01:22,300 --> 00:01:23,690
kedudukan sebelumnya.

24
00:01:23,690 --> 00:01:26,970
Oleh itu, kita pada mulanya mempunyai 15 dan
SUSUTAN kaunter.

25
00:01:26,970 --> 00:01:30,065
Demikian maka kita akan menyerahhakkan 14 kepada
kedudukan depan, kaunter susutan,

26
00:01:30,065 --> 00:01:33,710
dan kita akan diberikan
13, dan sebagainya.

27
00:01:33,710 --> 00:01:37,620
>> Akhir sekali, kita perlu mengendalikan sudut yang
kes di mana, jika lembaga mempunyai walaupun

28
00:01:37,620 --> 00:01:44,450
dimensi, maka hanya melakukan 15, 14, 13,
12, semua jalan ke 3, 2, 1, adalah

29
00:01:44,450 --> 00:01:46,780
akan meninggalkan kita dengan
lembaga tidak dapat diselesaikan.

30
00:01:46,780 --> 00:01:49,390
Dan kita perlu menukar 1 dan 2.

31
00:01:49,390 --> 00:01:52,930
Jadi, jika d arena 2 sama dengan 0, itu
bagaimana kita akan memeriksa

32
00:01:52,930 --> 00:01:54,410
untuk melihat jika ia lebih.

33
00:01:54,410 --> 00:01:59,810
Jika d arena 2 sama dengan 0, maka berturut-turut d tolak
1, iaitu baris bawah, dan

34
00:01:59,810 --> 00:02:05,430
kedudukan d tolak 2, atau lajur d tolak
2, kita akan menetapkan bahawa untuk 2, dan

35
00:02:05,430 --> 00:02:07,860
ruangan d tolak 3 kami
akan menetapkan kepada 1.

36
00:02:07,860 --> 00:02:12,170
Jadi yang hanya menterbalikkan mana
1 dan 2 pada masa ini adalah.

37
00:02:12,170 --> 00:02:16,270
>> Akhir sekali, kita akan menetapkan sangat
bawah hak yang sama rata untuk kosong, di mana

38
00:02:16,270 --> 00:02:20,700
kosong telah hash ditakrifkan
di bahagian atas sebagai 0.

39
00:02:20,700 --> 00:02:26,785
Jadi, yang tidak tegas perlu,
kerana ini untuk gelung akan mempunyai

40
00:02:26,785 --> 00:02:30,610
terletak betul-betul bahagian bawah ke 0, kerana
kaunter secara semula jadi akan mencapai 0.

41
00:02:30,610 --> 00:02:34,610
Tetapi itu bergantung kepada kita mengetahui bahawa
kosong telah dicincang untuk mencari 0.

42
00:02:34,610 --> 00:02:38,280
Jika saya pergi ke program ini dan kemudian
menukar kosong di bahagian atas untuk 100, ia

43
00:02:38,280 --> 00:02:39,770
masih harus bekerja.

44
00:02:39,770 --> 00:02:43,180
>> Jadi ini hanya memastikan bahawa
kanan bawah adalah sebenarnya sama dengan kita

45
00:02:43,180 --> 00:02:44,870
nilai kosong.

46
00:02:44,870 --> 00:02:50,270
Akhir sekali, kita mempunyai dua pembolehubah global,
i dan kosong j supaya kosong, dan kita lihat

47
00:02:50,270 --> 00:02:53,360
mereka diisytiharkan di bahagian atas.

48
00:02:53,360 --> 00:02:56,270
Dan kita akan menggunakan kedua-dua global
pembolehubah untuk mengesan

49
00:02:56,270 --> 00:02:59,040
kedudukan kosong, supaya kita tidak
perlu melihat melalui keseluruhan

50
00:02:59,040 --> 00:03:03,890
lembaga untuk mencari yang kosong setiap tunggal
kali kita cuba untuk membuat satu langkah.

51
00:03:03,890 --> 00:03:08,450
Jadi kedudukan kosong sentiasa adalah
akan mula di sebelah kanan bawah.

52
00:03:08,450 --> 00:03:13,270
Jadi kanan bawah diberikan oleh
indeks d tolak 1, d tolak 1.

53
00:03:13,270 --> 00:03:14,880
Jadi, itulah init.

54
00:03:14,880 --> 00:03:17,040
>> Sekarang kita beralih untuk menarik.

55
00:03:17,040 --> 00:03:19,370
Jadi, cabutan akan menjadi sama
di mana kita akan melelar

56
00:03:19,370 --> 00:03:20,970
atas seluruh lembaga.

57
00:03:20,970 --> 00:03:25,400
Dan kita hanya mahu mencetak nilai
yang di setiap posisi lembaga.

58
00:03:25,400 --> 00:03:29,580
Jadi di sini, kita mencetak nilai itulah
pada setiap kedudukan lembaga.

59
00:03:29,580 --> 00:03:32,280
Dan melihat bahawa kita lakukan -.

60
00:03:32,280 --> 00:03:37,410
Dan itu hanya memberitahu printf yang
tidak kira jika ia adalah satu angka satu atau

61
00:03:37,410 --> 00:03:42,010
dua digit, kita masih mahu ia
mengambil dua tiang di cetak keluar,

62
00:03:42,010 --> 00:03:46,290
supaya jika kita mempunyai dua digit dan satu
nombor digit pada papan yang sama, kami

63
00:03:46,290 --> 00:03:49,450
papan masih akan kelihatan bagus dan persegi.

64
00:03:49,450 --> 00:03:54,190
>> Oleh itu, kita mahu berbuat demikian untuk setiap nilai
dalam lembaga, kecuali kosong.

65
00:03:54,190 --> 00:03:58,260
Jadi, jika kedudukan dalam lembaga sama
kosong, maka kita secara khusus

66
00:03:58,260 --> 00:04:01,730
ingin mencetak hanya garis bawah
untuk mewakili kosong, bukan

67
00:04:01,730 --> 00:04:05,150
apa sahaja nilai
kosong sebenarnya.

68
00:04:05,150 --> 00:04:08,500
>> Akhir sekali, kita ingin mencetak
keluar barisan baru.

69
00:04:08,500 --> 00:04:11,970
Perhatikan bahawa ini adalah masih di dalam
luar untuk gelung, tetapi di luar

70
00:04:11,970 --> 00:04:13,200
dalam untuk gelung.

71
00:04:13,200 --> 00:04:17,930
Sejak luar ini untuk gelung iterating
ke atas semua baris, dan sebagainya printf ini

72
00:04:17,930 --> 00:04:22,130
akan hanya mencetak barisan baru, jadi kita
bergerak untuk mencetak barisan seterusnya.

73
00:04:22,130 --> 00:04:23,910
Dan itu sahaja untuk cabutan.

74
00:04:23,910 --> 00:04:27,770
>> Jadi, mari kita beralih untuk bergerak.

75
00:04:27,770 --> 00:04:32,590
Sekarang, kita lulus bergerak, jubin bahawa
pengguna dimasukkan dalam permainan - mereka

76
00:04:32,590 --> 00:04:36,360
memasukkan jubin yang mereka mahu untuk bergerak - dan
anda sepatutnya kembali bool, jadi

77
00:04:36,360 --> 00:04:39,300
sama ada benar atau salah, bergantung kepada
sama ada langkah yang sebenarnya

78
00:04:39,300 --> 00:04:43,360
sah - sama ada jubin yang boleh
berpindah ke ruang yang kosong.

79
00:04:43,360 --> 00:04:48,340
>> Jadi di sini, kita mengisytiharkan pembolehubah tempatan,
tile_1 dan tile_j, yang akan

80
00:04:48,340 --> 00:04:52,150
sama dengan blank_i dan blank_j,
kecuali ia akan mengesan

81
00:04:52,150 --> 00:04:54,910
kedudukan jubin.

82
00:04:54,910 --> 00:05:00,370
Sekarang di sini, kita akan menggunakan blank_i
dan blank_j dan berkata semua betul, jadi

83
00:05:00,370 --> 00:05:01,930
inilah kosong di papan.

84
00:05:01,930 --> 00:05:04,420
>> Sekarang, adalah jubin di atas kosong?

85
00:05:04,420 --> 00:05:06,210
Adakah jubin di sebelah kiri kosong?

86
00:05:06,210 --> 00:05:07,420
Adakah jubin di sebelah kanan kosong?

87
00:05:07,420 --> 00:05:08,970
Adakah jubin di bawah kosong?

88
00:05:08,970 --> 00:05:13,330
Jadi, jika jubin adalah dalam mana-mana
kedudukan, maka kita tahu bahawa jubin

89
00:05:13,330 --> 00:05:16,390
boleh berpindah ke tempat yang kosong dan
kosong yang boleh dipindahkan ke mana

90
00:05:16,390 --> 00:05:18,240
jubin kini.

91
00:05:18,240 --> 00:05:26,400
>> Jadi di sini, kita katakan jika lembaga pada kedudukan
blank_i tolak 1 blank_j.

92
00:05:26,400 --> 00:05:31,120
Jadi ini mengatakan adalah jubin
di atas kosong semasa?

93
00:05:31,120 --> 00:05:34,350
Dan jika demikian, kita akan ingat
yang kedudukan jubin.

94
00:05:34,350 --> 00:05:37,870
Jubin yang berada dalam kedudukan blank_i
tolak 1 dan blank_j.

95
00:05:37,870 --> 00:05:40,660
kini pertama, kami juga mempunyai semak ini
di sini, jadi blank_i adalah

96
00:05:40,660 --> 00:05:41,760
lebih besar daripada 0.

97
00:05:41,760 --> 00:05:43,410
>> Mengapa kita mahu berbuat demikian?

98
00:05:43,410 --> 00:05:47,290
Nah, jika kosong adalah di baris atas
lembaga, maka kita tidak mahu

99
00:05:47,290 --> 00:05:51,240
melihat di atas kosong untuk jubin sejak
ada apa-apa di atas bahagian atas

100
00:05:51,240 --> 00:05:52,430
deretan papan.

101
00:05:52,430 --> 00:05:55,950
Ini adalah bagaimana anda mungkin berakhir mendapat
sesuatu seperti bersalah segmentasi atau

102
00:05:55,950 --> 00:05:59,030
program anda hanya mungkin bekerja
dalam cara yang tidak dijangka.

103
00:05:59,030 --> 00:06:04,310
Jadi, ini adalah memastikan bahawa kita tidak
melihat di tempat-tempat yang tidak sah.

104
00:06:04,310 --> 00:06:08,470
>> Sekarang kita akan melakukan perkara yang sama untuk
semua kemungkinan kombinasi yang lain.

105
00:06:08,470 --> 00:06:13,250
Jadi di sini, kita sedang mencari di bawah kosong
untuk melihat jika itu jubin.

106
00:06:13,250 --> 00:06:16,950
Dan kita juga perlu memastikan kami
tidak pada baris bawah, jika tidak kita

107
00:06:16,950 --> 00:06:18,910
tidak perlu mencari jubin.

108
00:06:18,910 --> 00:06:25,040
Di sini, kita akan melihat di sebelah kiri
kosong untuk melihat jika ia jubin.

109
00:06:25,040 --> 00:06:27,860
Dan kita tidak perlu melihat ke kiri
jika kita dalam ruang paling kiri.

110
00:06:27,860 --> 00:06:30,100
Dan di sini kita akan melihat kepada
kanan kosong, dan kita tidak harus

111
00:06:30,100 --> 00:06:33,340
melihat ke kanan jika kita
dalam ruang paling kanan.

112
00:06:33,340 --> 00:06:37,820
>> Jadi, jika tidak ada perkara-perkara benar,
bermakna jubin tidak bersebelahan

113
00:06:37,820 --> 00:06:39,640
kepada kosong dan kita boleh kembali palsu.

114
00:06:39,640 --> 00:06:41,230
Langkah itu tidak sah.

115
00:06:41,230 --> 00:06:47,010
Tetapi, jika salah seorang daripada mereka itu benar, maka di
ketika ini, kita tahu tile_i itu dan

116
00:06:47,010 --> 00:06:50,540
tile_j adalah sama dengan
kedudukan jubin.

117
00:06:50,540 --> 00:06:55,210
Dan sebagainya, kita boleh mengemas kini lembaga di
jawatan tile_i dan tile_j.

118
00:06:55,210 --> 00:06:59,820
Kita tahu nilai baru akan menjadi kosong
dan bahawa blank_i kedudukan

119
00:06:59,820 --> 00:07:02,950
blank_j, yang asal
kosong - kami tahu jubin akan

120
00:07:02,950 --> 00:07:04,030
bergerak di sana.

121
00:07:04,030 --> 00:07:07,610
>> Notis kita sebenarnya tidak perlu melakukan
swap sebenar di sini, kerana kita tahu

122
00:07:07,610 --> 00:07:09,850
nilai-nilai yang perlu dimasukkan
ke dalam kedudukan itu.

123
00:07:09,850 --> 00:07:13,780
Kami tidak memerlukan sementara
berubah-ubah sekitar.

124
00:07:13,780 --> 00:07:16,920
>> Akhir sekali, kita perlu ingat kita yang
mempunyai pembolehubah global kami yang

125
00:07:16,920 --> 00:07:18,980
mengesan kedudukan
daripada kosong.

126
00:07:18,980 --> 00:07:22,780
Oleh itu, kita ingin mengemaskini kedudukan
kosong untuk di mana jubin

127
00:07:22,780 --> 00:07:24,190
asalnya adalah.

128
00:07:24,190 --> 00:07:27,680
Akhir sekali, kita kembali benar kerana
langkah itu berjaya.

129
00:07:27,680 --> 00:07:31,110
Kami telah berjaya menukar
kosong dengan jubin.

130
00:07:31,110 --> 00:07:34,890
>> Baiklah, kita jadi lepas
perlu menyemak won.

131
00:07:34,890 --> 00:07:39,900
Jadi, memenangi juga kembali bool di mana
benar akan menunjukkan bahawa

132
00:07:39,900 --> 00:07:41,460
pengguna telah memenangi permainan.

133
00:07:41,460 --> 00:07:43,780
Dan palsu yang menunjukkan bahawa
permainan ini masih berterusan.

134
00:07:43,780 --> 00:07:46,340
Pengguna tidak menang.

135
00:07:46,340 --> 00:07:52,100
Jadi, ini akan menjadi cukup banyak
bertentangan dengan INIT, di mana INIT,

136
00:07:52,100 --> 00:07:56,920
ingat, kita memulakan lembaga
15, 14, 13, 12, sebagainya.

137
00:07:56,920 --> 00:08:03,000
Manakala menang, kita mahu untuk memeriksa jika
lembaga adalah 1, 2, 3, 4, 5, dan sebagainya.

138
00:08:03,000 --> 00:08:06,600
>> Jadi, kita akan memulakan kami
melawan untuk 1 kerana itulah yang utama di

139
00:08:06,600 --> 00:08:08,400
kiri lembaga harus.

140
00:08:08,400 --> 00:08:10,860
Dan kemudian kita akan gelung
atas seluruh lembaga.

141
00:08:10,860 --> 00:08:13,690
Mari kita mengabaikan keadaan ini
untuk kali kedua.

142
00:08:13,690 --> 00:08:18,410
Dan keadaan ini hanya akan
cek adalah lembaga pada kedudukan ini

143
00:08:18,410 --> 00:08:20,790
sama dengan tuduhan semasa?

144
00:08:20,790 --> 00:08:27,040
Jika ya, kenaikan kiraan supaya
kedudukan seterusnya kita melihat adalah salah satu yang lebih tinggi

145
00:08:27,040 --> 00:08:29,690
daripada kedudukan kita berada di sekarang.

146
00:08:29,690 --> 00:08:32,700
>> Jadi itulah bagaimana kita mendapat
kiri atas adalah 1 orang.

147
00:08:32,700 --> 00:08:33,950
Kenaikan kiraan untuk 2.

148
00:08:33,950 --> 00:08:35,010
Lihatlah kedudukan seterusnya.

149
00:08:35,010 --> 00:08:35,690
Adakah ini 2?

150
00:08:35,690 --> 00:08:37,659
Jika ya, kenaikan kiraan 3.

151
00:08:37,659 --> 00:08:39,179
Kedudukan Seterusnya, adakah ini 3?

152
00:08:39,179 --> 00:08:42,440
Jika ya, kenaikan kiraan
untuk 4, dan sebagainya.

153
00:08:42,440 --> 00:08:49,190
Jadi, jika ada apa-apa kedudukan di
lembaga yang tidak sama kiraan kita,

154
00:08:49,190 --> 00:08:52,640
maka kita mahu kembali palsu kerana itu
bermakna ada beberapa jubin yang

155
00:08:52,640 --> 00:08:55,490
tidak dalam kedudukan yang betul.

156
00:08:55,490 --> 00:08:58,810
>> Jadi di sini, apa yang keadaan ini lakukan?

157
00:08:58,810 --> 00:09:02,170
Nah, ingat bahawa kosong itu
sepatutnya pergi di sebelah kanan bawah.

158
00:09:02,170 --> 00:09:06,180
Dan nilai kosong tidak mungkin
semestinya bersamaan dengan nilai

159
00:09:06,180 --> 00:09:11,080
melawan yang akan dicapai
di sebelah kanan bawah.

160
00:09:11,080 --> 00:09:15,760
Oleh itu, kita secara khusus mahu untuk memeriksa jika i
sama sama d tolak 1 dan j setaraf

161
00:09:15,760 --> 00:09:19,470
sama d tolak 1 - yang mengatakan jika kita
mencari di kanan bawah

162
00:09:19,470 --> 00:09:22,050
lembaga - maka kita hanya
mahu terus.

163
00:09:22,050 --> 00:09:26,200
Kami mahu melangkau ini tertentu
lelaran untuk gelung.

164
00:09:26,200 --> 00:09:31,250
>> Justeru, jika kita berjaya melalui ini
bersarang untuk gelung, ini bermakna bahawa

165
00:09:31,250 --> 00:09:34,690
tiada jubin yang di dalam
kedudukan yang tidak betul.

166
00:09:34,690 --> 00:09:38,900
Dan kita keluar daripada gelung dan datang
di sini, di mana kita boleh kembali benar.

167
00:09:38,900 --> 00:09:41,800
Semua jubin berada di kedudukan yang betul
dan itu bererti pengguna mempunyai

168
00:09:41,800 --> 00:09:43,230
memenangi permainan.

169
00:09:43,230 --> 00:09:44,460
Dan itu sahaja.

170
00:09:44,460 --> 00:09:46,550
Nama saya Rob Bowden, dan ini adalah 15.

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