naiden93
05-28-2008, 19:08
Значи ако може да ми помогнете със решението на тази задача(трябва да бъде на C++):
K рицари, номерирани с числата от 1 до K, завладели далечен остров с правоъгълна форма. Като се раздели островът с хоризонтални и вертикални линии на квадратчета с еднакъв размер, се получава мрежа с M реда и N стълба. Някои от квадратчетата са заети от суша, а други – от блата. Блатата не били интересни за никого, тъй като през тях нито можело да се премине, нито можело да се обработват. Всеки от рицарите си построил замък върху сушата, който заемал едно квадратче. Никои два замъка не били в едно и също квадратче.
Рицарите решили да разделят сушата на K царства, като всяко квадратче суша да влезе в царството на този от рицарите, чийто замък е най-близо до това квадратче. Разстоянието от замък до някое квадратче е дължината на най-късия път между тях, не минаващ през блата, измерена в брой квадратчета. Придвижването става само от квадратче в съседно на него квадратче. За всяко квадратче съседни са тези, с които то има обща страна.
Ако едно квадратче е на равно разстояние от замъците на двама или повече рицари, то се включва в царството на този от тях, който е с най-малък номер. Всяко квадратче суша може да се достигне от поне един замък.
Напишете програма KING.EXE, която определя от колко квадратчета ще се състои царството на всеки рицар.
От първия ред на стандартния вход се четат 3 числа: броят на рицарите K
(1 < K < 10) и размерите на острова M и N (1 < M, N < 100). На всеки от следващите K реда са задедни номерът на ред i и номерът на стълб j на квадратчето, в което се намира замъкът на поредния рицар (в реда на номерата им), 1 <= i <= M, 1 <= j <= N. Следващите M реда задават картата на острова, като всеки ред съдържа по N числа 0 или 1, разделени с по един интервал. Нулите задават квадратче заето от суша, а единиците – от блата.
На стандартния изход да се изведат K числа, по едно число на ред – броят квадратчета в царството на поредния рицар.
ПРИМЕР
Вход Изход
2 5 5 8
1 1 12
1 5
0 0 1 0 0
1 0 1 0 0
0 0 1 0 0
0 1 0 0 0
0 0 0 0 0
K рицари, номерирани с числата от 1 до K, завладели далечен остров с правоъгълна форма. Като се раздели островът с хоризонтални и вертикални линии на квадратчета с еднакъв размер, се получава мрежа с M реда и N стълба. Някои от квадратчетата са заети от суша, а други – от блата. Блатата не били интересни за никого, тъй като през тях нито можело да се премине, нито можело да се обработват. Всеки от рицарите си построил замък върху сушата, който заемал едно квадратче. Никои два замъка не били в едно и също квадратче.
Рицарите решили да разделят сушата на K царства, като всяко квадратче суша да влезе в царството на този от рицарите, чийто замък е най-близо до това квадратче. Разстоянието от замък до някое квадратче е дължината на най-късия път между тях, не минаващ през блата, измерена в брой квадратчета. Придвижването става само от квадратче в съседно на него квадратче. За всяко квадратче съседни са тези, с които то има обща страна.
Ако едно квадратче е на равно разстояние от замъците на двама или повече рицари, то се включва в царството на този от тях, който е с най-малък номер. Всяко квадратче суша може да се достигне от поне един замък.
Напишете програма KING.EXE, която определя от колко квадратчета ще се състои царството на всеки рицар.
От първия ред на стандартния вход се четат 3 числа: броят на рицарите K
(1 < K < 10) и размерите на острова M и N (1 < M, N < 100). На всеки от следващите K реда са задедни номерът на ред i и номерът на стълб j на квадратчето, в което се намира замъкът на поредния рицар (в реда на номерата им), 1 <= i <= M, 1 <= j <= N. Следващите M реда задават картата на острова, като всеки ред съдържа по N числа 0 или 1, разделени с по един интервал. Нулите задават квадратче заето от суша, а единиците – от блата.
На стандартния изход да се изведат K числа, по едно число на ред – броят квадратчета в царството на поредния рицар.
ПРИМЕР
Вход Изход
2 5 5 8
1 1 12
1 5
0 0 1 0 0
1 0 1 0 0
0 0 1 0 0
0 1 0 0 0
0 0 0 0 0