Дарси гузашта савол чунин буд: «гирду атрофи ин катак чист?» Акнун саволҳо калонтаранд: ҳамаи чароғҳо чанд катакро равшан мекунанд, мӯҳра то куҷо лағжида метавонад, ду мӯҳраро бо чанд роҳ ҷойгир кардан мумкин аст.
Нишонаҳо дар шабакаи дуюм
Вақте чанд чиз ба як катакҳо таъсир мекунад, шабакаи дуюми bool нигоҳ доред ва катакҳоро фавран нашуморед, балки нишон диҳед. Катаке, ки ду бор расидаанд, ҳамоно як бор нишон дода шудааст.
Толор шабакаи
n × mаст:Lчароғ,.фарш аст. Чароғ катаки худро ва чор катаки паҳлӯи онро равшан мекунад. Чанд катак равшан аст?
Вуруд
Баромад
Ду чароғ катакро дар сатри 2, сутуни 4 равшан мекунанд, аммо он як бор ҳисоб мешавад. Барнома нишонаҳоро дар охир мешуморад. Агар {0, 0}-ро ҳамчун қадами аввал ба dr ва dc илова кунед, як сикл катаки худи чароғро низ равшан мекунад.
Гузаштан то девор
Баъзе саволҳо ба як самт то ҳадди имкон мераванд: рух то куҷо лағжида метавонад, аз ин ҷо чанд катакро дидан мумкин аст? Ин сикли while аст, ки як қадамро такрор ба такрор мегирад, то даме ки катаки оянда дар дохили шабака ва холӣ бошад:
Тартиби санҷишҳо муҳим аст. && дар аввалин қисми ноҳақ меистад, бинобар ин g[nr][nc] танҳо вақте хонда мешавад, ки маълум аст катак дар дохил аст.
Ҳисоб кардани ҷойгиркуниҳо
«Ду мӯҳраро бо чанд роҳ ҷойгир кардан мумкин аст?» Роҳ ҷуфти катакҳост. Катакҳои тахтаи n × n-ро аз 0 то n * n - 1 сатр ба сатр рақам кунед. Катаки p дар сатри p / n ва сутуни p % n аст, қоидаи гузариш аз дарси ҷадвалҳо. Ду сикл, барои ҳар мӯҳра як дона, ҳар ҷуфтро месанҷанд. Инак ду шоҳе, ки набояд ба ҳам расанд, ҳатто дар кунҷ:
Ду шоҳи якхела дар тахтаи
n × nтавре меистанд, ки ба ҳам намерасанд. Онҳо бо чанд роҳ истода метавонанд?
Вуруд
Баромад
Шоҳҳо якхела мебошанд, бинобар ин ҳар ҷойгиркунӣ ду бор ёфта мешавад: ҳамчун (катаки p, катаки q) ва ҳамчун (катаки q, катаки p). Шумора дар охир ба 2 тақсим мешавад. Як катак ду бор ҳеҷ гоҳ ҳисоб намешавад: ду тафовути он 0 ва 0 аст, на аз 1 калонтар.
Шумо метавонед чор сикл низ нависед, барои r1, c1, r2 ва c2. Шумора ҳамон аст. Дар тахтаи n × n ин n⁴ қадам аст: барои n = 50 6 250 000, ки зуд аст.
Барои мӯҳраҳои дигар танҳо шарт иваз мешавад. Ду рух ҳамдигарро дар як сатр ё як сутун мезананд. Ду фил ҳамдигарро дар диагонали умумӣ мезананд: . Агар ҷуфтҳоеро ҳисоб кунед, ки ҳамдигарро , як катаки ду бор худ аз худ меафтад, зеро катак бо сатр, сутун ва диагонали худ як аст. Эҳтиёт шавед: барои мӯҳрае, ки як катаки такрорӣ «задан» ҳисоб намешавад, -ро худатон гузаред.
