MNYC '17: ASCII Art II

View as PDF
Submit solution
Points: 5
Time limit: 1.0s
Memory limit: 256M
Author:
aurpine
Problem type

After playing around with the ASCII Art program you made, aurpine wonders…

If you were to only use the draw dot and change colour commands, what is the least number of operations required to recreate a drawing?

To refresh your memory, the draw dot operation draws a single character at the specified coordinate (anywhere you want). The change colour operation changes the colour, or character that operations use. The default colour is .. The canvas is initially blank (filled with   characters).

Input Specification

The first line will contain two space separated integers, C R (1 \le C, R \le 100), the number of columns and rows of the drawing.

The next R lines will contain C characters. Note that the character may be a space.

Output Specification

Output a single integer, the minimum number of operations.

Sample Input 1

5 3
.|...
.|  .
.+--.

Sample Output 1

16

Explanation for Sample Output 1

Using the default colour, draw the 8 outer dots.

. ...
.   .
.   .

Then change the colour and draw the column (1 colour change + 2 draw dots)

.|...
.|  .
.   .

Then change the colour and draw the cross (1 colour change + 1 draw dot)

.|...
.|  .
.+  .

Then change the colour and draw the horizontal line (1 colour change and 2 draw dots)

.|...
.|  .
.+--.

That is 1 + 1 + 1 colour changes + (8 + 2 + 1 + 2 = 13) draw dots for a total of 16 operations.

Sample Input 2

11 6
  / / / ,  
 xxxxxxxx  
x O >->-xx-
x  >->->-x 
 XX XxX Xx`
  XXX XXX

Sample Output 2

51

Comments


  • 0
    onlyIfStatement  commented on Jan. 7, 2017, 7:31 p.m. ← edited

    do they have the same restrictions as ASCII art?

    not really necessary, sorry if i confused anyone


    • 1
      aurpine  commented on Jan. 7, 2017, 8:17 p.m.

      Yes, added.