Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Некада, не толико давно, на једном факултету не толико далеко, чувени Исидор је усликао повећи број слика својом “MST”-камером. Међутим, он сада има жељу да те фотографије сам развије, а за то му је потребно да простор буде таман (са акцентом на прво а). Да би то урадио, оградиће неки део своје дневне собе и у њему ће искључити сва светла и бацити се на посао.
Исидорова дневна соба се може замислити као матрица \(N\times M\), и има помало необичан распоред лампи и прекидача у њој. Наиме, у сваком пољу те матрице се налази по једна лампа, која је на почетку или искључена или укључена, што значи да има укупно \(M\cdot N\) лампи. Он такође има \((M-1)\cdot (N-1)\) прекидача који се налазе у тачкама пресека линија које одређују матрицу, и они мењају стање лампама у свим пољима у чијем су ћошку. Формалније, за свако \(1\le i\le N-1\) и \(1\le j\le M-1\) постоји прекидач који мења стања (искључено у укључено, и обрнуто) лампама \((i,j), (i+1,j), (i,j+1), (i+1,j+1)\). Исидор ће оградити једну подматрицу као своју собу за развијање слика.
Исидор каже да је подматрица мрачна соба уколико је могуће да после ограђивања користећи прекидаче строго унутар те собе начини да су све лампе у соби искључене. Ово значи да не сме да дира прекидаче који мењају стање лампама ван ограђене подматрице. Он је то већ одавно урадио и већ увелико развија фотографије, али га ипак интересује тачан број начина на који је могао да огради такву подматрицу.
Потребно је да имплементирате функцију
где су \(M\) и \(N\) бројеви који представљају број колона и врста у \(A\), а \(A\) је матрица у чијем пољу \((i,j)\) пише број \(0\) уколико је лампа на пољу \((i,j)\) почетку искључена, а \(1\) уколико је на почетку укључена. Индекси матрице почињу од 1. ## Пример
Нека је \(N=2\), \(M=3\) и нека је \(A\): ~~~ 0 1 1 0 1 1 ~~~ Тада је укупан број мрачних соба \(5\), и то су собе - Само поље \((1,1)\) - Само поље \((2,1)\) - Подматрица од поља \((1,1)\) и \((2,1)\) - Подматрица од поља \((1,2)\), \((2,2)\), \((1,3)\) и \((2,3)\) - Цела матрица
Прве три већ на почетку имају све угашене лампе, док за друге две је могуће активитирати прекидач који мења стање лампама на пољима \((1,2)\), \((2,2)\), \((1,3)\) и \((2,3)\).
Потребно је да пошаљете тачно један фајл mracna_soba.cpp
који имплементира поменуту функцију. Осим тражене функције, ваш фајл
може садржати и додатне глобалне променљиве, помоћне функције и додатне
библиотеке.
Ваша функција мора бити следећег облика:
long long Prebroj(int N, int M, int** A);
Вашим програмима је дозвољено да мењају садржај низова/матрица, али не смеју да приступају ван граница датих низова.
Уз задатак, обезбеђен вам је “template” фајл code.cpp
које можете користити и мењати по потреби. Такође вам је обезбеђен
програм grader.cpp који служи да лакше тестирате кодове.
Овај програм учитава са стандардног улаза следеће податке:
Затим овај програм зове вашу функцију и штампа број који врати функција.