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

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

3
00:00:13,715 --> 00:00:17,800
Ég er Rob og ég vona þín
leikur fyrir leik 15.

4
00:00:17,800 --> 00:00:22,040
Nú, það eru fjórir aðgerðir sem þú þarft
að innleiða í þessari áætlun - init,

5
00:00:22,040 --> 00:00:24,650
teikna, færa, og vann.

6
00:00:24,650 --> 00:00:27,230
Svo skulum við líta á init.

7
00:00:27,230 --> 00:00:32,930
>> Hér sjáum við það fyrsta sem við erum
að fara að gera er að lýsa yfir breytu

8
00:00:32,930 --> 00:00:34,600
heitir gegn.

9
00:00:34,600 --> 00:00:37,620
Það er að fara að frumstilla
til d sinnum D mínus 1.

10
00:00:37,620 --> 00:00:40,200
Mundu að d er vídd
í stjórn okkar.

11
00:00:40,200 --> 00:00:43,840
Hvernig init er að fara að vinna er það er að fara
að iterate yfir umræðuborðinu

12
00:00:43,840 --> 00:00:46,050
og við erum að fara að byrja
efst til vinstri.

13
00:00:46,050 --> 00:00:48,570
>> Og við skulum bara segja að við
hafa 4 af 4 borð.

14
00:00:48,570 --> 00:00:51,220
Svo efst til vinstri við erum
að fara að segja er 15.

15
00:00:51,220 --> 00:00:53,960
Og þá erum við bara að fara að telja
gegnum stjórnum, segja 15, 14, 13,

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

17
00:00:58,510 --> 00:01:03,780
Þannig að efsta vinstri, búast við að vera d sinnum
D mínus 1, sem á 4 með því 4

18
00:01:03,780 --> 00:01:08,290
Málið er að fara að vera 16 mínus
1, sem er rétt 15.

19
00:01:08,290 --> 00:01:10,885
>> Og nú er hér þar sem við erum að fara að
iterate yfir umræðuborðinu.

20
00:01:10,885 --> 00:01:14,720
Og við erum að fara að setja hverja stöðu í
borð til núvirði

21
00:01:14,720 --> 00:01:19,090
gegn okkar, og þá gegn er að fara
til þess að telja, svo að næsta

22
00:01:19,090 --> 00:01:22,300
stöðu við náum er að fara að hafa
gegn að vera einn minna en

23
00:01:22,300 --> 00:01:23,690
fyrri stöðu.

24
00:01:23,690 --> 00:01:26,970
Þannig að við þurftum í upphafi 15 og
lækka gegn.

25
00:01:26,970 --> 00:01:30,065
Svo þá erum við að fara að úthluta 14 við
Næsta staða, lækka gegn,

26
00:01:30,065 --> 00:01:33,710
og við erum að fara að úthlutað
13, og svo framvegis.

27
00:01:33,710 --> 00:01:37,620
>> Að lokum, þurfum við að takast á horninu
ræða þar, ef stjórnin hefur enn

28
00:01:37,620 --> 00:01:44,450
vídd, þá bara að gera 15, 14, 13,
12, alla leið niður í 3, 2, 1, er

29
00:01:44,450 --> 00:01:46,780
að fara að yfirgefa okkur
er unsolvable borð.

30
00:01:46,780 --> 00:01:49,390
Og við verðum að skipta um 1 og 2.

31
00:01:49,390 --> 00:01:52,930
Svo ef d unga fólkið 2 jafngildir 0, það er
hvernig við ætlum að athuga

32
00:01:52,930 --> 00:01:54,410
til að sjá hvort það er jafnvel.

33
00:01:54,410 --> 00:01:59,810
Ef d unga fólkið 2 jafngildir 0, þá í röð d mínus
1, sem er neðri röðinni, og

34
00:01:59,810 --> 00:02:05,430
Afstaða D mínus 2, eða Dálkur D mínus
2, við erum að fara að setja það í 2, og

35
00:02:05,430 --> 00:02:07,860
Dálkur D mínus 3 við erum
að fara að setja í 1.

36
00:02:07,860 --> 00:02:12,170
Svo það er bara snúið þar
1 og 2 eru eins og er.

37
00:02:12,170 --> 00:02:16,270
>> Að lokum, við erum að fara að setja mjög
neðst til hægri jafn autt, þar

38
00:02:16,270 --> 00:02:20,700
autt hefur verið tæti skilgreint
efst jafnt og 0.

39
00:02:20,700 --> 00:02:26,785
Svo, það var ekki brýna nauðsyn,
þar sem þetta fyrir lykkja er að fara að hafa

40
00:02:26,785 --> 00:02:30,610
setja neðst til hægri til 0, síðan
gegn vilja náttúrulega ná 0.

41
00:02:30,610 --> 00:02:34,610
En það treystir á okkur vita að
autt var kjötkássa til að finna a 0.

42
00:02:34,610 --> 00:02:38,280
Ef ég fer inn í þessa áætlun og síðar
breyta auðan efst á 100, það

43
00:02:38,280 --> 00:02:39,770
ætti enn að vinna.

44
00:02:39,770 --> 00:02:43,180
>> Þannig að þetta er bara að ganga úr skugga um að
neðst til hægri er í raun jafn okkar

45
00:02:43,180 --> 00:02:44,870
autt gildi.

46
00:02:44,870 --> 00:02:50,270
Að lokum, höfum við tvær alheims breytur,
svo autt ég og eyða J, og við sjáum

47
00:02:50,270 --> 00:02:53,360
þá lýsti efst.

48
00:02:53,360 --> 00:02:56,270
Og við erum að fara að nota þá tveimur alþjóðlegum
breytur til að halda utan um

49
00:02:56,270 --> 00:02:59,040
staða auða, svo að við gerum ekki
þurfa að horfa í gegnum allt

50
00:02:59,040 --> 00:03:03,890
borð að finna auða hvert einasta
tíma við að reyna að hreyfa sig.

51
00:03:03,890 --> 00:03:08,450
Þannig að staða á óunna efninu alltaf er
fara að byrja neðst til hægri.

52
00:03:08,450 --> 00:03:13,270
Svo the botn réttur er gefið með
tölur, 1 d-mínus 1, d mínus.

53
00:03:13,270 --> 00:03:14,880
Svo, það er init.

54
00:03:14,880 --> 00:03:17,040
>> Nú erum við að fara á að draga.

55
00:03:17,040 --> 00:03:19,370
Svo draga er að fara að vera svipuð
þar sem við erum að fara að iterate

56
00:03:19,370 --> 00:03:20,970
yfir umræðuborðinu.

57
00:03:20,970 --> 00:03:25,400
Og við viljum bara að prenta verðmæti
sem er í hverja stöðu borð.

58
00:03:25,400 --> 00:03:29,580
Svo hér erum við prentun á gildi sem
í hverja stöðu borð.

59
00:03:29,580 --> 00:03:32,280
Og taka eftir því að við erum að gera -.

60
00:03:32,280 --> 00:03:37,410
Og það er bara að segja printf sem
Óháð því hvort það er einn tölustafur eða

61
00:03:37,410 --> 00:03:42,010
tveggja stafa tölu, viljum við samt að
taka upp tvo dálka í prenta út,

62
00:03:42,010 --> 00:03:46,290
þannig að ef við höfum tveggja stafa og einn
stafa númer í sama borð, okkar

63
00:03:46,290 --> 00:03:49,450
Stjórnin mun enn líta ágætur og ferningur.

64
00:03:49,450 --> 00:03:54,190
>> Þannig að við viljum gera það fyrir hvert gildi
að stjórn, nema fyrir auða.

65
00:03:54,190 --> 00:03:58,260
Svo er, ef stöðu á borð jafngildir
auða, þá erum við sérstaklega

66
00:03:58,260 --> 00:04:01,730
vilt prenta út bara undirstrika
til að tákna autt, í stað þess að

67
00:04:01,730 --> 00:04:05,150
hvað gildi sem
auður í raun er.

68
00:04:05,150 --> 00:04:08,500
>> Að lokum viljum við að prenta
út nýja línu.

69
00:04:08,500 --> 00:04:11,970
Takið eftir að þetta er enn inni
ytri fyrir lykkju, en utan

70
00:04:11,970 --> 00:04:13,200
innri for lykkju.

71
00:04:13,200 --> 00:04:17,930
Þar sem þetta ytri fyrir lykkja er iterating
yfir allar færslur, og svo er þetta printf

72
00:04:17,930 --> 00:04:22,130
að fara að prenta bara nýja línu, þannig að við
fara að prenta út næsta róður.

73
00:04:22,130 --> 00:04:23,910
Og það er það fyrir jafntefli.

74
00:04:23,910 --> 00:04:27,770
>> Svo, nú skulum fara að færa.

75
00:04:27,770 --> 00:04:32,590
Nú, fara við færa, flísar að
notandi er færð í leiknum - þeir

76
00:04:32,590 --> 00:04:36,360
slá inn flísar sem þeir vilja til að færa - og
þú ert ímyndaður til að skila bool, svo

77
00:04:36,360 --> 00:04:39,300
annaðhvort satt eða ósatt, eftir
hvort sem ferðinni var í raun

78
00:04:39,300 --> 00:04:43,360
Gildir - hvort sem flísar geta verið
flutti inn í auða pláss.

79
00:04:43,360 --> 00:04:48,340
>> Svo hér, lýsa við staðbundna breytu,
tile_1 og tile_j, sem eru að fara að

80
00:04:48,340 --> 00:04:52,150
vera svipuð blank_i og blank_j,
nema það er að fara að halda utan um

81
00:04:52,150 --> 00:04:54,910
staða flísar.

82
00:04:54,910 --> 00:05:00,370
Nú hér erum við að fara að nota blank_i
og blank_j og segja allt í lagi, svo

83
00:05:00,370 --> 00:05:01,930
hér er autt á borðinu.

84
00:05:01,930 --> 00:05:04,420
>> Nú er flísar ofan auða?

85
00:05:04,420 --> 00:05:06,210
Er flísar til vinstri á auða?

86
00:05:06,210 --> 00:05:07,420
Er flísar til hægri á auða?

87
00:05:07,420 --> 00:05:08,970
Er flísar neðan auða?

88
00:05:08,970 --> 00:05:13,330
Svo er, ef flísar er í hverri sem er af þeim
stöður, þá vitum vér, að flísar

89
00:05:13,330 --> 00:05:16,390
er hægt að færa inn í auða stað og
eyðuna má færa til þar sem

90
00:05:16,390 --> 00:05:18,240
flísar er nú.

91
00:05:18,240 --> 00:05:26,400
>> Svo hér, segjum við ef stjórn á stöðu
blank_i mínus 1 blank_j.

92
00:05:26,400 --> 00:05:31,120
Þannig að þetta er að segja er flísar
ofan við núverandi autt?

93
00:05:31,120 --> 00:05:34,350
Og ef svo er, erum við að fara að muna
sem er staðsetning á flísar.

94
00:05:34,350 --> 00:05:37,870
Flísar er í stöðu blank_i
mínus 1 og blank_j.

95
00:05:37,870 --> 00:05:40,660
nú fyrst, höfum við einnig þessa ávísun
hérna, svo blank_i er

96
00:05:40,660 --> 00:05:41,760
stærra en 0.

97
00:05:41,760 --> 00:05:43,410
>> Hvers vegna viljum við gera það?

98
00:05:43,410 --> 00:05:47,290
Jæja, ef autt er í efstu röð
stjórnar, þá viljum við ekki að

99
00:05:47,290 --> 00:05:51,240
líta ofan auða fyrir flísar síðan
það er ekkert fyrir ofan við efsta

100
00:05:51,240 --> 00:05:52,430
röð af borðinu.

101
00:05:52,430 --> 00:05:55,950
Þetta er hvernig þú might endir upp getting
eitthvað eins og skiptingu kenna eða

102
00:05:55,950 --> 00:05:59,030
program gæti bara vinna
í óvænta vegu.

103
00:05:59,030 --> 00:06:04,310
Svo þetta er að tryggja að við gerum ekki
líta á stöðum sem eru ekki gild.

104
00:06:04,310 --> 00:06:08,470
>> Nú við erum að fara að gera það sama fyrir
allar aðrar mögulegar samsetningar.

105
00:06:08,470 --> 00:06:13,250
Svo hér erum við að leita hér að neðan auða
til að sjá hvort það er flísar.

106
00:06:13,250 --> 00:06:16,950
Og við verðum einnig að tryggja að við erum
ekki á neðri röðinni, eða annað sem við

107
00:06:16,950 --> 00:06:18,910
ætti ekki að líta á flísar.

108
00:06:18,910 --> 00:06:25,040
Hér erum við að fara að horfa til vinstri
auða til að sjá hvort það er flísar.

109
00:06:25,040 --> 00:06:27,860
Og við ættum ekki að líta til vinstri
ef við erum í dálknum lengst til vinstri.

110
00:06:27,860 --> 00:06:30,100
Og hér erum við að fara að horfa til
rétt af öskjunni, og við ættum ekki

111
00:06:30,100 --> 00:06:33,340
líta til hægri ef við erum
í rightmost dálki.

112
00:06:33,340 --> 00:06:37,820
>> Svo, ef enginn af þessum hlutum væri satt,
sem þýðir að flísar voru ekki samliggjandi

113
00:06:37,820 --> 00:06:39,640
til autt og við getum return false.

114
00:06:39,640 --> 00:06:41,230
Ferðinni var ekki gild.

115
00:06:41,230 --> 00:06:47,010
En, ef einn af þeim væri satt, þá á
þetta lið, við vitum að tile_i og

116
00:06:47,010 --> 00:06:50,540
tile_j eru jafn
staða flísar.

117
00:06:50,540 --> 00:06:55,210
Og svo getum við uppfæra úr stjórninni á
stöður tile_i og tile_j.

118
00:06:55,210 --> 00:06:59,820
Við vitum að ný gildi verður autt
og að staða blank_i

119
00:06:59,820 --> 00:07:02,950
blank_j, sem var upprunalega
autt - við vitum flísar er að fara að

120
00:07:02,950 --> 00:07:04,030
flytja þangað.

121
00:07:04,030 --> 00:07:07,610
>> Taka við í raun ekki að gera
alvöru skipti hér, þar sem við vitum að

122
00:07:07,610 --> 00:07:09,850
gildum sem þurfa að vera sett
í þessum stöðum.

123
00:07:09,850 --> 00:07:13,780
Við þurfa ekki tímabundna
breytu í kring.

124
00:07:13,780 --> 00:07:16,920
>> Að lokum, þurfum við að muna að við
hafa alheims breytur sem eiga

125
00:07:16,920 --> 00:07:18,980
halda utan um stöðu
af öskjunni.

126
00:07:18,980 --> 00:07:22,780
Þannig að við viljum að uppfæra stöðu
eyðuna til að vera þar sem flísar

127
00:07:22,780 --> 00:07:24,190
upphaflega var.

128
00:07:24,190 --> 00:07:27,680
Að lokum, aftur við satt þar
ferðinni var vel.

129
00:07:27,680 --> 00:07:31,110
Við skipti tekist að
autt með flísum.

130
00:07:31,110 --> 00:07:34,890
>> Allt í lagi, svo síðasta sem við
þarf að athuga vann.

131
00:07:34,890 --> 00:07:39,900
Svo vann álíka skilar bool þar
satt er að fara að gefa til kynna að

132
00:07:39,900 --> 00:07:41,460
notandi hefur unnið leikinn.

133
00:07:41,460 --> 00:07:43,780
Og falskur er bendir til þess að
leikurinn er enn í gangi.

134
00:07:43,780 --> 00:07:46,340
Notandinn hefur ekki unnið.

135
00:07:46,340 --> 00:07:52,100
Svo, þetta er að fara að vera ansi mikið
andstæða init, þar init,

136
00:07:52,100 --> 00:07:56,920
Mundu, við frumstillt borð
til 15, 14, 13, 12, svo á.

137
00:07:56,920 --> 00:08:03,000
En vann, viljum við að athuga hvort
borð er 1, 2, 3, 4, 5, og svo framvegis.

138
00:08:03,000 --> 00:08:06,600
>> Svo erum við að fara að frumstilla okkar
gegn 1 þar sem það er það sem efst

139
00:08:06,600 --> 00:08:08,400
vinstri stjórnar ættu að vera.

140
00:08:08,400 --> 00:08:10,860
Og þá erum við að fara að lykkja
yfir umræðuborðinu.

141
00:08:10,860 --> 00:08:13,690
Skulum hunsa þetta ástand
fyrir a second.

142
00:08:13,690 --> 00:08:18,410
Og þetta ástand er bara að fara að
stöðva er um borð í þessari stöðu

143
00:08:18,410 --> 00:08:20,790
jafnt og núverandi talningu?

144
00:08:20,790 --> 00:08:27,040
Ef svo er, hækka talningu þannig að
Næsta staða sem við skoðum er eitt hærri

145
00:08:27,040 --> 00:08:29,690
en þeirri stöðu sem við erum á núna.

146
00:08:29,690 --> 00:08:32,700
>> Svo er það hvernig við fáum
efst til vinstri ætti að vera 1.

147
00:08:32,700 --> 00:08:33,950
Vöxtur talningu í 2.

148
00:08:33,950 --> 00:08:35,010
Horfðu á næstu stöðu.

149
00:08:35,010 --> 00:08:35,690
Er þetta 2?

150
00:08:35,690 --> 00:08:37,659
Ef svo er, hækka á talningu til 3.

151
00:08:37,659 --> 00:08:39,179
Næsta staða, er þetta 3?

152
00:08:39,179 --> 00:08:42,440
Ef svo er, hækka á talningu
til 4, og svo framvegis.

153
00:08:42,440 --> 00:08:49,190
Svo ef það er einhver staða á
borð sem er ekki jafnt telja okkar,

154
00:08:49,190 --> 00:08:52,640
þá viljum við return false þar sem
þýðir að það er einhver flísar sem er

155
00:08:52,640 --> 00:08:55,490
ekki í réttri stöðu.

156
00:08:55,490 --> 00:08:58,810
>> Svo hér, hvað er þetta ástand að gera?

157
00:08:58,810 --> 00:09:02,170
Jæja, muna að blank
átti að fara á the botn réttur.

158
00:09:02,170 --> 00:09:06,180
Og gæti gildi í auða er ekki
endilega jöfn gildi á

159
00:09:06,180 --> 00:09:11,080
gegn það er að fara að vera náð
neðst til hægri.

160
00:09:11,080 --> 00:09:15,760
Þannig að við viljum sérstaklega til að athuga hvort ég
jafngildir jafngildir D mínus 1 og j jafn

161
00:09:15,760 --> 00:09:19,470
jafngildir d mínus 1 - sem er að segja ef við
eru að horfa á the botn réttur af

162
00:09:19,470 --> 00:09:22,050
stjórnin - þá erum við bara
langar að halda áfram.

163
00:09:22,050 --> 00:09:26,200
Við viljum sleppa þessu tiltekna
endurtekning á for lykkju.

164
00:09:26,200 --> 00:09:31,250
>> Og svo, ef við stjórna til fá í gegnum þetta
hreiður fyrir lykkju, sem þýðir að

165
00:09:31,250 --> 00:09:34,690
það var engin flísar sem var í
að röng staðsetning.

166
00:09:34,690 --> 00:09:38,900
Og við brjótast út úr lykkja og koma
hér, þar sem við getum aftur satt.

167
00:09:38,900 --> 00:09:41,800
Allar flísar voru í rétta stöðu
og það þýðir að notandinn hefur

168
00:09:41,800 --> 00:09:43,230
vann leikinn.

169
00:09:43,230 --> 00:09:44,460
Og það er það.

170
00:09:44,460 --> 00:09:46,550
Mitt nafn er Rob Bowden, og þetta var 15.

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