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

2
00:00:13,070 --> 00:00:13,715
>> ROB BOWDEN: Hei.

3
00:00:13,715 --> 00:00:17,800
Olen Rob, ja toivon teidän
peli peli 15.

4
00:00:17,800 --> 00:00:22,040
Nyt on neljä toimintoa tarvitset
toteuttaa tätä ohjelmaa - init,

5
00:00:22,040 --> 00:00:24,650
piirtää, liikkua, ja voitti.

6
00:00:24,650 --> 00:00:27,230
Joten katsokaamme init.

7
00:00:27,230 --> 00:00:32,930
>> Täällä näemme ensimmäinen asia olemme
aikoo tehdä, on julistaa muuttuja

8
00:00:32,930 --> 00:00:34,600
nimeltään laskuri.

9
00:00:34,600 --> 00:00:37,620
Se tulee alustaa
d kertaa d miinus 1.

10
00:00:37,620 --> 00:00:40,200
Muista, että d on ulottuvuus
meidän aluksella.

11
00:00:40,200 --> 00:00:43,840
Kuinka init on menossa töihin on se menee
kerrata koko keskustelufoorumilla

12
00:00:43,840 --> 00:00:46,050
ja aiomme aloittaa
ylhäällä vasemmalla.

13
00:00:46,050 --> 00:00:48,570
>> Ja haluan vain sanoa, me
on 4 4 aluksella.

14
00:00:48,570 --> 00:00:51,220
Niin ylhäällä vasemmalla olemme
aikoo sanoa on 15.

15
00:00:51,220 --> 00:00:53,960
Ja sitten me vain odotamme laskea
kautta levyt, sanoi 15, 14, 13,

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

17
00:00:58,510 --> 00:01:03,780
Joten vasemmassa yläkulmassa, odotamme olevan d kertaa
d miinus 1, joka 4 4

18
00:01:03,780 --> 00:01:08,290
tapauksessa tulee olemaan 16 miinus
1, mikä on oikein 15.

19
00:01:08,290 --> 00:01:10,885
>> Ja nyt täällä on, jos aiomme
kerrata koko järjestelmässä.

20
00:01:10,885 --> 00:01:14,720
Ja me aiomme tehdä kunkin aseman
hallituksen nykyinen arvo

21
00:01:14,720 --> 00:01:19,090
vastatoimia, ja sitten vasta tulee
dekrementoidaan siten, että seuraava

22
00:01:19,090 --> 00:01:22,300
kanta pääsemme joutuu
counter olla yksi vähemmän kuin

23
00:01:22,300 --> 00:01:23,690
edelliseen asentoon.

24
00:01:23,690 --> 00:01:26,970
Joten meillä oli aluksi 15 ja
vähentääksesi laskuri.

25
00:01:26,970 --> 00:01:30,065
Niin aiomme antaa 14
seuraavaan paikkaan, vähenemä laskuri,

26
00:01:30,065 --> 00:01:33,710
ja aiomme valittu
13, ja niin edelleen.

27
00:01:33,710 --> 00:01:37,620
>> Lopuksi, meidän täytyy käsitellä, että nurkkaan
tapauksessa, jos hallitus on jopa

28
00:01:37,620 --> 00:01:44,450
ulottuvuus, sitten vain tehdä 15, 14, 13,
12, kaikki alas 3, 2, 1, on

29
00:01:44,450 --> 00:01:46,780
aio jättää meille
ratkaisematon aluksella.

30
00:01:46,780 --> 00:01:49,390
Ja meillä on vaihtaa 1 ja 2.

31
00:01:49,390 --> 00:01:52,930
Joten, jos d mod 2 on 0, se
miten aiomme tarkistaa

32
00:01:52,930 --> 00:01:54,410
onko se edes.

33
00:01:54,410 --> 00:01:59,810
Jos d mod 2 on 0, niin rivillä d miinus
1, joka on alarivissä, ja

34
00:01:59,810 --> 00:02:05,430
asennossa d miinus 2 tai sarake d miinus
2, aiomme asettaa, että 2 ja

35
00:02:05,430 --> 00:02:07,860
sarake d miinus 3 olemme
menossa asetettu 1.

36
00:02:07,860 --> 00:02:12,170
Niin että on vain peruutettaessa jossa
1 ja 2 tällä hetkellä ovat.

37
00:02:12,170 --> 00:02:16,270
>> Lopuksi, aiomme asettaa hyvin
Alhaalla oikealla yhtä tyhjä, jos

38
00:02:16,270 --> 00:02:20,700
tyhjä on hash määritelty
yläosassa kuin 0.

39
00:02:20,700 --> 00:02:26,785
Niin, se ei ollut ehdottoman välttämätöntä,
koska tämä silmukka joutuu

40
00:02:26,785 --> 00:02:30,610
asettaa alhaalta oikealla 0, koska
laskuri luonnollisesti saavuttaa 0.

41
00:02:30,610 --> 00:02:34,610
Mutta joka luottaa meihin tietäen, että
Aihio hajauttamat löytää 0.

42
00:02:34,610 --> 00:02:38,280
Jos menen tähän ohjelmaan ja myöhemmin
muuttaa tyhjän ruudun yläosassa 100, se

43
00:02:38,280 --> 00:02:39,770
pitäisi silti toimia.

44
00:02:39,770 --> 00:02:43,180
>> Joten tämä on vain varmistaa, että
Alhaalla oikealla on oikeastaan ​​sama kuin meidän

45
00:02:43,180 --> 00:02:44,870
Nolla-arvoa.

46
00:02:44,870 --> 00:02:50,270
Lopuksi, meillä on kaksi globaaleja muuttujia,
niin tyhjä i ja tyhjä j, ja näemme

47
00:02:50,270 --> 00:02:53,360
ilmoitettuja huipulla.

48
00:02:53,360 --> 00:02:56,270
Ja aiomme käyttää näitä kahta globaalia
muuttujat seurata

49
00:02:56,270 --> 00:02:59,040
asema tyhjäksi, jolloin emme
täytyy käydä läpi koko

50
00:02:59,040 --> 00:03:03,890
aluksella löytää tyhjän joka ikinen
aikaa yritämme tehdä liikkua.

51
00:03:03,890 --> 00:03:08,450
Joten kanta aihion aina on
aikoo aloittaa oikeassa alareunassa.

52
00:03:08,450 --> 00:03:13,270
Joten oikeassa alareunassa annetaan
indeksit d miinus 1, d miinus 1.

53
00:03:13,270 --> 00:03:14,880
Niin, että on init.

54
00:03:14,880 --> 00:03:17,040
>> Nyt siirrymme piirtää.

55
00:03:17,040 --> 00:03:19,370
Niin, piirtää tulee olemaan samanlainen
minne olemme menossa kerrata

56
00:03:19,370 --> 00:03:20,970
koko järjestelmässä.

57
00:03:20,970 --> 00:03:25,400
Ja me vain haluamme tulostaa arvon
joka on kunkin asennon hallituksen.

58
00:03:25,400 --> 00:03:29,580
Joten tässä, me tulostus arvon, joka on
kuhunkin asentoon hallituksen.

59
00:03:29,580 --> 00:03:32,280
Ja huomaa, että me teemme -.

60
00:03:32,280 --> 00:03:37,410
Ja juuri kertoo printf että
riippumatta, jos se on yhden numeron tai

61
00:03:37,410 --> 00:03:42,010
kaksinumeroinen luku, haluamme kuitenkin sen
kestää jopa kaksi saraketta tulostaa,

62
00:03:42,010 --> 00:03:46,290
niin, että jos meillä on kaksinumeroinen ja yksi
luvuin samassa hallituksessa, meidän

63
00:03:46,290 --> 00:03:49,450
lauta edelleen hyvältä yleinen.

64
00:03:49,450 --> 00:03:54,190
>> Joten haluamme tehdä, että jokaisen arvon
hallituksessa, lukuun ottamatta tyhjä.

65
00:03:54,190 --> 00:03:58,260
Joten, jos asema hallituksessa vastaa
tyhjä, niin me nimenomaan

66
00:03:58,260 --> 00:04:01,730
haluat tulostaa vain alaviiva
edustaa tyhjä, sen sijaan, että

67
00:04:01,730 --> 00:04:05,150
arvosta riippumatta
tyhjä todellisuudessa on.

68
00:04:05,150 --> 00:04:08,500
>> Lopuksi haluamme tulostaa
ulos uusi rivi.

69
00:04:08,500 --> 00:04:11,970
Huomaa, että tämä on vielä sisällä
ulompi silmukka, mutta sen ulkopuolella

70
00:04:11,970 --> 00:04:13,200
sisempi silmukka.

71
00:04:13,200 --> 00:04:17,930
Koska tämä ulompi silmukka on iteroimalla
yli kaikki rivit, ja niin tämä printf on

72
00:04:17,930 --> 00:04:22,130
menossa vain tulostaa uuden rivin, joten
siirtyä tulostaa seuraavalle riville.

73
00:04:22,130 --> 00:04:23,910
Ja se on siinä tasapeli.

74
00:04:23,910 --> 00:04:27,770
>> Joten, nyt lähdetään siitä liikkua.

75
00:04:27,770 --> 00:04:32,590
Nyt, ohitamme liikkua, laatta, joka
Käyttäjä on merkitty peli - ne

76
00:04:32,590 --> 00:04:36,360
Kirjoita laatta he haluavat siirtyä - ja
sinun pitäisi palata bool, joten

77
00:04:36,360 --> 00:04:39,300
joko tosi tai epätosi riippuen
onko tämä siirto oli todella

78
00:04:39,300 --> 00:04:43,360
voimassa - onko tämä laatta voi olla
muutti välilyönti.

79
00:04:43,360 --> 00:04:48,340
>> Joten tässä, me julistamme paikallinen muuttuja,
tile_1 ja tile_j, jotka ovat menossa

80
00:04:48,340 --> 00:04:52,150
olla samanlainen blank_i ja blank_j,
paitsi se tulee seurata

81
00:04:52,150 --> 00:04:54,910
asema laatta.

82
00:04:54,910 --> 00:05:00,370
Nyt täällä, aiomme käyttää blank_i
ja blank_j ja sanoa kunnossa, joten

83
00:05:00,370 --> 00:05:01,930
tässä on tyhjä taululle.

84
00:05:01,930 --> 00:05:04,420
>> Nyt on laatta yläpuolella tyhjä?

85
00:05:04,420 --> 00:05:06,210
Onko laatta vasemmalla tyhjä?

86
00:05:06,210 --> 00:05:07,420
Onko laatta oikealla tyhjä?

87
00:05:07,420 --> 00:05:08,970
Onko laattojen alla tyhjä?

88
00:05:08,970 --> 00:05:13,330
Joten, jos laatta on jossakin näistä
kantoja, niin tiedämme, että laatta

89
00:05:13,330 --> 00:05:16,390
voidaan siirtää osaksi tyhjää kohtaa ja
aihio voidaan siirtää, jos

90
00:05:16,390 --> 00:05:18,240
laatta tällä hetkellä on.

91
00:05:18,240 --> 00:05:26,400
>> Joten tässä, sanomme jos aluksella asennossa
blank_i miinus 1 blank_j.

92
00:05:26,400 --> 00:05:31,120
Joten tämä sanoo, laatta
nykyisen yläpuolella tyhjä?

93
00:05:31,120 --> 00:05:34,350
Ja jos näin on, aiomme muistaa
että kanta on laatta.

94
00:05:34,350 --> 00:05:37,870
Laatta on sijalla blank_i
miinus 1 ja blank_j.

95
00:05:37,870 --> 00:05:40,660
nyt ensin, meillä on myös tämä tarkastus
täällä, joten blank_i on

96
00:05:40,660 --> 00:05:41,760
suurempi kuin 0.

97
00:05:41,760 --> 00:05:43,410
>> Miksi haluamme tehdä niin?

98
00:05:43,410 --> 00:05:47,290
No, jos aihio on ylärivissä
Hallituksen, niin emme halua

99
00:05:47,290 --> 00:05:51,240
katso edellä aihio laatta vuodesta
ei ole mitään yläpuolella

100
00:05:51,240 --> 00:05:52,430
rivi aluksella.

101
00:05:52,430 --> 00:05:55,950
Näin saatat päätyä saada
jotain segmentointi vika tai

102
00:05:55,950 --> 00:05:59,030
ohjelma saattaa vain toimia
odottamattomalla tavalla.

103
00:05:59,030 --> 00:06:04,310
Niin, tämä on varmistaa, että emme
katso paikoissa, jotka eivät kelpaa.

104
00:06:04,310 --> 00:06:08,470
>> Nyt aiomme tehdä saman asian
kaikki muut mahdolliset yhdistelmät.

105
00:06:08,470 --> 00:06:13,250
Joten tässä, me etsimme alla tyhjän
onko se laatta.

106
00:06:13,250 --> 00:06:16,950
Ja meillä on myös varmistaa, että olemme
ei alarivillä, tai muuten

107
00:06:16,950 --> 00:06:18,910
ei pitäisi etsiä laatta.

108
00:06:18,910 --> 00:06:25,040
Täällä aiomme katsoa vasemmalla
tyhjäksi nähdä, jos se on laatta.

109
00:06:25,040 --> 00:06:27,860
Ja meidän ei pitäisi katsoa vasemmalle
jos olemme vasemmassa reunassa.

110
00:06:27,860 --> 00:06:30,100
Ja tässä me aiomme katsoa
oikeus tyhjäksi, ja meidän ei pitäisi

111
00:06:30,100 --> 00:06:33,340
katsoa oikealle, jos olemme
oikeanpuoleisessa sarakkeessa.

112
00:06:33,340 --> 00:06:37,820
>> Joten, jos mitään näistä asioista olisi totta,
se tarkoittaa, että laatta ei ollut vieressä

113
00:06:37,820 --> 00:06:39,640
tyhjälle ja voimme palata vääriä.

114
00:06:39,640 --> 00:06:41,230
Tilanne ei ollut pätevä.

115
00:06:41,230 --> 00:06:47,010
Mutta jos yksi niistä olisi totta, sitten
Tässä vaiheessa tiedämme, että tile_i ja

116
00:06:47,010 --> 00:06:50,540
tile_j ovat yhtä kuin
asema laatta.

117
00:06:50,540 --> 00:06:55,210
Ja niin, voimme päivittää aluksella
kannat tile_i ja tile_j.

118
00:06:55,210 --> 00:06:59,820
Tiedämme uusi arvo on tyhjä
ja että kannan blank_i

119
00:06:59,820 --> 00:07:02,950
blank_j, joka oli alkuperäinen
blank - tiedämme laatta on menossa

120
00:07:02,950 --> 00:07:04,030
liikkua siellä.

121
00:07:04,030 --> 00:07:07,610
>> Huomaa emme oikeastaan ​​tarvitse tehdä
todellinen swap täällä, koska tiedämme

122
00:07:07,610 --> 00:07:09,850
-arvot, jotka on lisättävä
noihin kantoja.

123
00:07:09,850 --> 00:07:13,780
Emme tarvitse väliaikaisia
muuttujan ympärille.

124
00:07:13,780 --> 00:07:16,920
>> Lopuksi, meidän täytyy muistaa, että me
on meidän globaaleja muuttujia, jotka ovat

125
00:07:16,920 --> 00:07:18,980
pitää kirjaa kannan
aihion.

126
00:07:18,980 --> 00:07:22,780
Joten haluamme päivittää aseman
tyhjän olla siellä, missä laatta

127
00:07:22,780 --> 00:07:24,190
alun perin oli.

128
00:07:24,190 --> 00:07:27,680
Lopuksi palaamme totta, sillä
siirto oli onnistunut.

129
00:07:27,680 --> 00:07:31,110
Olemme onnistuneesti vaihtaa
tyhjä kanssa laatta.

130
00:07:31,110 --> 00:07:34,890
>> Okei, niin viime me
täytyy tarkistaa wonia.

131
00:07:34,890 --> 00:07:39,900
Joten, voitti samalla palauttaa bool jossa
totta on menossa osoittaa, että

132
00:07:39,900 --> 00:07:41,460
käyttäjä on voittanut pelin.

133
00:07:41,460 --> 00:07:43,780
Ja vääriä on osoittaa, että
Peli on vielä kesken.

134
00:07:43,780 --> 00:07:46,340
Käyttäjä ei ole voittanut.

135
00:07:46,340 --> 00:07:52,100
Niin, tämä tulee olemaan aika paljon
vastakohta init, jossa init,

136
00:07:52,100 --> 00:07:56,920
Muistan, me alustaa hallituksessa
15, 14, 13, 12, niin edelleen.

137
00:07:56,920 --> 00:08:03,000
Kun taas voitti, haluamme tarkistaa, jos
aluksella on 1, 2, 3, 4, 5, ja niin edelleen.

138
00:08:03,000 --> 00:08:06,600
>> Joten, aiomme alustaa meidän
Counter 1 koska sitähän alkuun

139
00:08:06,600 --> 00:08:08,400
vasemmalla hallituksen pitäisi olla.

140
00:08:08,400 --> 00:08:10,860
Ja sitten me aiomme silmukka
koko järjestelmässä.

141
00:08:10,860 --> 00:08:13,690
Katsotaanpa sivuuttaa tämän ehdon
toista.

142
00:08:13,690 --> 00:08:18,410
Ja tämä ehto on juuri menossa
tarkastus on aluksella tässä asennossa

143
00:08:18,410 --> 00:08:20,790
vastaa nykyistä laskee?

144
00:08:20,790 --> 00:08:27,040
Jos näin on, inkrementoidaan laskenta siten, että
seuraavaan paikkaan katsomme on yksi suurempi

145
00:08:27,040 --> 00:08:29,690
kuin kannan olemme juuri nyt.

146
00:08:29,690 --> 00:08:32,700
>> Niin, että miten saamme
vasemmassa yläkulmassa on 1.

147
00:08:32,700 --> 00:08:33,950
Inkrementoidaan laskenta 2.

148
00:08:33,950 --> 00:08:35,010
Katsokaa seuraavaan kohtaan.

149
00:08:35,010 --> 00:08:35,690
Onko tämä 2?

150
00:08:35,690 --> 00:08:37,659
Jos näin on, inkrementoidaan laskenta 3.

151
00:08:37,659 --> 00:08:39,179
Seuraava asema, on tämä 3?

152
00:08:39,179 --> 00:08:42,440
Jos näin on, inkrementoidaan laskenta
4, ja niin edelleen.

153
00:08:42,440 --> 00:08:49,190
Joten, jos on kanta
aluksella, joka ei vastaa meidän luottaa,

154
00:08:49,190 --> 00:08:52,640
Sitten haluamme palata väärä koska
tarkoittaa, että on joitakin laatta, joka on

155
00:08:52,640 --> 00:08:55,490
ei ole oikeassa asennossa.

156
00:08:55,490 --> 00:08:58,810
>> Joten tässä, mitä tämä ehto tekee?

157
00:08:58,810 --> 00:09:02,170
No, muista, että aihio on
tarkoitus mennä alas oikealle.

158
00:09:02,170 --> 00:09:06,180
Ja tyhjä arvo ei ehkä
välttämättä ole sama arvo

159
00:09:06,180 --> 00:09:11,080
laskuri, joka tulee saavuttaa
oikeassa alareunassa.

160
00:09:11,080 --> 00:09:15,760
Joten me nimenomaan haluat tarkistaa, jos i
vastaa yhtä suuri kuin d miinus 1 ja j tasavertaisina

161
00:09:15,760 --> 00:09:19,470
vastaa d miinus 1 - joka sanoo, jos me
etsivät oikeassa alakulmassa

162
00:09:19,470 --> 00:09:22,050
lauta - sitten me vain
haluavat jatkaa.

163
00:09:22,050 --> 00:09:26,200
Haluamme ohittaa tämän erityisen
iterointia silmukan.

164
00:09:26,200 --> 00:09:31,250
>> Ja niin, jos onnistumme saamaan läpi tämän
sisäkkäisiä silmukka, se tarkoittaa, että

165
00:09:31,250 --> 00:09:34,690
ei ollut laatta, joka oli
väärään asentoon.

166
00:09:34,690 --> 00:09:38,900
Ja rikomme ulos silmukan ja tulevat
täällä, missä me voimme palata totta.

167
00:09:38,900 --> 00:09:41,800
Kaikki laatat olivat oikeilla paikoillaan
ja se tarkoittaa käyttäjällä on

168
00:09:41,800 --> 00:09:43,230
voitti pelin.

169
00:09:43,230 --> 00:09:44,460
Ja se on siinä.

170
00:09:44,460 --> 00:09:46,550
Nimeni on Rob Bowden, ja tämä oli 15.

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