Примерна задача за изпит C# 2 – 3D Max Walk


5

 

Здравейте

Условието на задача е:

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.

 

Въпроса ми е как  от числото 7 се отива на 9 ? Ще се радвам ако някой може да ми разясни логиката на задачата.


в Софтуерна академия от Божидар Пенчев (0 точки)


Отговори



2
Здравей,
Когато решавах тази задача се чудех абсолютно същото нещо. След като я реших, игнорирайки примера (страшна грешка) и открих че гърми на много от тестовете, установих, че ключът се крие в следния ред:
"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."
Когато тръгнеш в 6те посоки, не взимаш предвид само кубчетата, съседни на настоящото, а *всички*, които лежат до края на кубчето в тези посоки. Т.е. в примера като тръгнеш от 7 надясно, сравняваш и 3 и 1 и 9, а не само 3. Реших задачата така и тръгна. :)

от AnnaSG (485 точки)


0
Между другото, сега погледнах и видях че задачата ми дава 90/100 като съм я решавала последно, така че може и нещо да пропускам :D Ако колегите имат други мнения, да ги споделят!

от AnnaSG (485 точки)

0
Сега вече разбирам. Благодаря ти за разяснението. Вече мога да започна да дерзая и аз по нея :) .

от Божидар Пенчев (0 точки)


0
Тъкмо я чопля и аз тази в момента :). Фактически трябва да провериш реда, колоната и каквото и да е третото измерение (тунел може би). И да вземеш най голямото изключвайки това на което си в момента. и освен това броя колко пъти се среща, и освен това да провериш дали вече не си го посещавал. :)
Edit: Няма да слагам код, но горе долу така се решава:
Тръгваш от средата акто си запазваш текущата точка и нейната стойност и си отбелязваш че си посетил тази точка (в друг bool масив). Търсиш по ред колона и тунел за най голяма, като когато намериш такава и запазваш стойността и координатите и си нлираш брояча за намерени най-големи точки. Ако намериш втора такава увеличаваш брояча на намерени еднакви точки, след като провериш в трите посоки ако брояча на намерени най-големи точки ти е равен на единица и намерената точка не е била посетена, прибавяш стойността и към посетените досега точки и си я отбелязваш като посетена. след това нулираш най-голямата намерена точка (по скоро я правиш -1001) защото има и отрицателни стойности в масива и нулираш брояча и и търсиш отново по ред колона и тунел с кординатитие на новата най-голяма точка. (това може да стане с един while цикъл)
Само още едно нещо, внимавай когато проверяваш да подминаваш текущата точка, защото така е по условие.
Това е горе долу моето решение, би ми било интересно да чуя и други идеи, ще помогнат със сигурност.

от nikola76 (1250 точки)


3

Разделил съм първия пример, за който питаш в 4 стъпки. Във всяка една стъпка с червено кръгче съм обелязал стартовата позиция, а със зелено изходната позиция. Bold стойностите определят кои числа участват при търсенето на максимална стойност, когато се намираме на дадена позиция. Започваме от центъра на куба - стъпка.1, цифрата в червеното кръгче.

Надявам се визуалното представяне и обяснението да ти помогне да разбереш как се движим.

Когато стигнем стойност 8 в стъпка.4, следващата най-висока стойност е 9, но тя вече е посетена, което означава принт и изход от програмата.


от nencho83 (538 точки)


0
Mного добре си го направил така нагледно. Благодаря ти!

от Божидар Пенчев (0 точки)


0
Аз четири часа я решавах тази задача, ако не бях видял в форума че може да продължават в дълботина до края на кубчето сигурно нямаше да се сетя и така имам 70/100 и гърми на тайм лимита :(
ето решението: http://pastebin.com/khzCLmkQ



0

Здравей! ;)

Има вече такава тема във форума :)

http://forums.academy.telerik.com/60051/c%23-sample-exam-2011-2012-3d-max-walk


от vlad0 (6103 точки)