[C#] Sample Exam 2011/2012 3D Max Walk


4

 

Be Problem 4 – 3D Max Walk

You are given a rectangular cuboid of size W (width), H (height) and D (depth) consisting of W * H * D cubes, each containing an integer number. A 3D max walk in the cuboid starts from the cube located at the cuboid's center (W, H and D are odd numbers). At each step the walk continues from the current cube in one of the 6 possible directions (left, right, up, down, deeper, shallower) to the cube which holds the maximal value among all possible cubes different than the current. The walk stops at some of the following conditions:

·        Several cubes hold the same maximal value.

·        There is only cube holding the maximal value but it is already visited (falls into a loop).

Your task is to write a program that finds the sum of the numbers in the cubes that are visited during the 3D max walk.

Input

The input data should be read from the console. At the first line 3 integers W, H and D are given separated by a space. These numbers specify the width, height and depth of the cuboid. At the next H lines the colors of the cubes in the cuboid are given as D sequences of exactly W integers. Each of these sequences consists of W integers separated by a single space. The sequences of W integers are separated one from another by " | " (space + vertical line + space).

The input data will be correct and there is no need to check it explicitly.

Output

The output data should be printed on the console.

At the first line of the output print the sum of the cubes visited by the 3D max walk.

Constraints

·        The numbers W, H and D are odd integers in the range [1…101].

·        The integers in the cuboid are in the range [-1000…1000]

·        Allowed work time for your program: 0.3 seconds.

·        Allowed memory: 16 MB.

Examples

Input

Output

 

Input

Output

5 3 3

3 4 1 9 1 | 0 1 2 3 8 | 1 2 5 6 7

2 7 3 1 9 | 2 5 5 2 1 | 8 6 3 5 8

1 8 2 1 5 | 9 1 3 8 6 | 4 5 6 3 2

34

3 3 1

1 2 3

5 6 4

8 4 5

19

At the first example the visited cubes are: 5 -> 5 -> 7 -> 9 -> 8. After 8 the maximal possible number is 9, which is already visited (falls into a loop). At the second example the visited cubes are 6 -> 5 -> 8. After 8 there are two maximal numbers (value 5) so the walk stops.

 

 

 

Решнието можете да откриете тук: http://pastebin.com/ns5JNwJs
Оставил съм тестовете ми, които съм използвал при първоначална обработка.
 
- създавам триизмерен масив, който можем да разглеждаме като поредица от двумерни масиви. Дължината на тази поредица ще наричаме дълбочина. Тези двумерни масиви ги наричам парчета /slices/, защото те са парчета от куба. Т.е. при куб [depth,row,col];
имаме depth на брой матрици с размери [row,col]
 
- условието изисква от нас да намерим най-голямото число на реда в текущия slice, на колоната в текущия slice и в ... сега стана интересно  ... в измерението образувана от кубчетата които са в дълбочина, т.е. трябва да обиколим в тези три посоки и да намерим най-голямото кубче из между тях трите без да включваме позицията на текущото.
 
- когато намерим най-голямото кубче трябва да го съберем с текущия тотал и да отбележим кубчето като използване. Това можем да направим с допълнителeн огледалeн по размери куб от булеви стойности. Default стойноста на bool е false, затова всеки път когато намерим Max, ще даваме на същата позиция в bool куба стойност true. Това ни гарантира, че следващия път когато намерим Max ще има къде да проверим дали сме използвали вече това кубче. Ако сме го използвали трябва да прекратим "разходката" и да изкараме сумата на конзолата.
 
- втората причина поради, която можем да прекратим "разходката" е две кубчета да имат максималната стойност - Маx. Затова преди да добавим Мах към крайната сума проверяваме дали повече от 1 кубче в съответните посоки има тази стойност, и съответно ако има изкарваме крайната сума на конзолата.
 
- При проверката нa посоките и редовете за максимална сума винаги имаме по 2 статични измерения. Когато проверяваме колоната на текущия slice, статични са ни column & slice, и проверяваме една и съща колона като сменяме само редовете. Съответно при проверката на реда на текущия slice, статични са ни row&slice и проверяваме един и същи ред като сменяме само клетките по колоните на текущия ред. За slice статични са row & col.
 
- Създавам три едномерни масива за всяка проверка на slice, row, col. Всеки от тези масиви съдържа 3 кординати + максималната стойност за съответното измерение. Т.е. масива съдържа следните елементи:
Позиция 0: slices
Позиция 1: rows
Позиция 2: cols
Позиция 3: maxNumber - първоначално инициализираме с -1111, което е по-малко от -1000 минималната стойност по условие, за да излизнем извън границите на стойностите. Това е за случай, например, ако стойността на първоначалната позиция/средата на куба/ съвпадне някоя от тези стойности програмата ще прекрати изпълнение, защото имаме две Max стойности.
 
Малко дълго се получи, но е 3ам и мисълта не ми тече гладко, по-скоро ръмбаво като кубче, ако имате въпроси или препоръки заповядайте :)
 

 




Отговори



1

Пускам и моето решение, за да ви покажа какво не трябва да правите... А то е: ДА НЕ ЧЕТЕТЕ УСЛОВИЕТО ДЕТАЙЛНО И НАПЪЛНО!

Точно защото го минах отгоре-отгоре, писах код, писах код, изгърмя, видях условието пак и за да не почвам отначало почнаха едни спагетизации и проблемации, които едвам ги докарах до 100/100. Резултата:

http://pastebin.com/qpUQr2hK

Мега излишни редове код се срещат тук. Извод: ВНИКВАЙТЕ В УСЛОВИЕТО! :)


от ivaylo.kenov (30760 точки)


0
През цялото време си мисля, че стъпката е център+-1 в шесте посоки.И ако излезеш от кубчето, то автоматично трябва да отидеш примерно ако си на позиция 0 височина да отидеш в макс височина :((((((((