Въпрос за задача от изпит по C# 2 - 3D Stars


0

Problem 4 – 3D Stars

You are given a rectangular cuboid of size W (width), H (height) and D (depth) consisting of W * H * D cubes, each colored in some color. Each color is denoted by a unique capital letter from the Latin alphabet: 'Y' is yellow, 'R' is red, 'B' is blue, 'G' green, etc. A 3D star is a figure of size 3 x 3 x 3 consisting of 7 cubes colored in the same color staying in the following configuration: one cube is the star center and 6 cubes are stuck at its 6 sides (see the figure below).

The figure below shows a sample cuboid consisting of 7 x 4 x 3 colored cubes (width = 7, height = 4, depth = 3) and how the 3D star figure looks like:

image

Your task is to write a program that finds how many 3D stars exist in the cuboid. At the cuboid above there are 4 stars: 3 yellow and 1 green. A cube is allowed to be shared between several stars.

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 letters. Each sequence of W letters is separated from the next with a single 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 total number of 3D stars in the cuboid. On the next few lines print the stars in the cuboid: color followed by a space and by amount found in the cuboid. Only colors with non-zero amount of stars should be listed. The colors should be listed in alphabetical order.

Constraints

  • The numbers W, H and D are all integers in the range [3…150].
  • The letter sequence in the input consists of capital Latin latters only
  • Allowed work time for your program: 0.25 seconds.
  • Allowed memory: 32 MB.

Examples

Input

Output

 

Input

Output

4 3 5

AAAA AAAA AAAA AAAA AAAA

AAAA AAAA AAAA AAAA AAAA

AAAA AAAA AAAA AAAA AAAA

6

A 6

7 4 3

BRYYYYY RYYYYGY YRYYYYY

YYYGBGY YYYYGGG YYYGGGY

RYBYGYY RYYYYGY RYBYGBB

RYBYGYY RBYYGYY RYBYGBB

4

G 1

Y 3

Решение: http://pastebin.com/02Ky6WiW

Колеги, тези от вас, които са решавали тази задача сигурно знаят от кое може да дава time limit. В моят случай дава на последните два теста и така и не мога да се сетя как да го направя за 100/100. Мерси предварително!

P.S. Не открих тема за тази задача във форума и затова отворих нова.




Отговори



1

Здрасти,

гледайки кода, това което ми идва на ум, е че метода CanAStarBeCalculated е малко излишен. Можеш да избегнеш нуждата от него, ако в трите фор цикъла в Main метода пуснеш индексите да започват от 1 и да се движат до width/height/depth - 1.

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




0
Това което колегата Мартин предложи е доста добра оптимизация, масивът работи доста по бързо от речника, но в този случай основното забавяне идва от другаде. Проблемът е, че ползваш стринг матрица. Ако смениш с char матрица минаваш всички тестове без други оптимизации. Предполагам всяко извикване на ToString(), което правиш във FillCuboid за всяка отделна клетка те бави повече от колкото би искал, в случаите когато куба е по-голям. Може и друга да е причината де, някои ако знае да каже :) Но отново и аз препоръчвам използването на масив за съхранение на резултата, въпреки че в случая не е от значение.


0
Прав беше за char матрицата, с нея минаха всички тестове. :)

от stefanN (952 точки)


1

Вместо речник използвай масив, ако искаш виж моето решение: http://pastebin.com/FQeY0P3Y

Масива ми е с дължина 26 бройки (колкото са буквите в английската азбука) и съхранява броя срещания на всяка буква. Примерно на индекс 0 ще е буквата 'A', на идекс 25 ще е 'Z'.

Как разбирам коя клетка да увелича с 1-ца, ако примерно текущата буква е 'D', ами по следният начин: stars[star - 'A']++; където star e буквата 'D', а stars е масива.


от martin.nikolov (4535 точки)


0
Благодаря колеги, ще пробвам с масив да я направя, а и булевият метод наистина е излишен в този случай. Поздрави!
Edit: Здравко, сега видях и съветът за char матрица и първо с това ще пробвам.
Мерси още веднъж!

от stefanN (952 точки)


1
Здравейте! Ето как я реших аз - http://pastebin.com/r1ekxvEg . Резултата го записвам в сортиран речник. По принцип заради това да е бързо правя проверка на 1 елемент и той ако не отговаря не продължава проверката, ако ли не продължава с проверка на следващ елемент.

от nikivat (246 точки)


0

Ето едно решение, което не използва тримерен масив, а само двумерен. Това е едно от малкото ми решения, които са по-кратки, по-бързи и заемат по-малко памет от авторското решение :D

Source: http://pastebin.com/M9iUMDe8


от neutrino (3376 точки)