2
\$\begingroup\$

Question

If you are currently on a cell with a value x, you can move to any cell in the same row or column, provided it has a value y such that x > y. This move is called a switch.

The input consists of:

  • two integers 0 < m,n < 50
  • an integer k indicating the number of switches allowed 0 < k < 20
  • an m by n grid filled with integers in the range -128 to 127

The output consists of:

  • a single integer r, indicating the minimum number of cells that have to be coloured red to satisfy the condition.

The condition is that:

  • if any cell is selected on the switchboard, it must be possible to
    • start at any red cell of your choice
    • make upto k switches
    • end up at the selected cell
  • the output must be reached within 60 seconds using any amount of memory.

Sample data

Inputs

(a) 7 8 10 
55 25 49 40 55 3 55
33 32 26 59 41 40 55
31 23 41 58 59 14 33
9 19 9 40 4 40 40
55 54 55 46 52 39 41
10 41 7 47 5 30 54
40 22 31 36 7 40 28
21 40 41 59 14 36 31

(b) 9 8 10
50 98 54 6 34 94 63 52 39
62 46 75 28 65 18 37 18 97
13 80 33 69 93 78 19 40 13
94 10 88 43 61 72 94 94 94
41 79 82 27 71 62 57 67 34
8 93 2 12 93 52 91 86 93
94 79 64 43 32 94 42 91 9
25 73 29 31 19 70 58 12 11

(c) 10 9 10
50 54 6 34 78 63 52 39 41 46
75 28 65 18 37 18 13 80 33 69
78 19 40 13 10 43 61 72 13 46
56 41 79 82 27 71 62 57 67 81
8 71 2 12 52 81 1 79 64 81
32 41 9 25 73 29 31 19 41 58
12 11 41 66 63 14 39 71 38 16
71 43 70 27 78 71 76 37 57 12
77 50 41 81 31 38 24 25 24 81

Outputs

(a) 9
(b) 9
(c) 8

Winning

You may use any language. Shortest code wins.

\$\endgroup\$
  • 8
    \$\begingroup\$ Am I missing something, or are the sample inputs missing m,n,k? \$\endgroup\$ – Geobits Oct 27 '15 at 13:03
  • \$\begingroup\$ @Geobits Oh, yes. I forgot to add it. \$\endgroup\$ – ghosts_in_the_code Oct 27 '15 at 15:59
  • \$\begingroup\$ What exactly is a switchboard? How does it relate to this challenge? \$\endgroup\$ – ASCIIThenANSI Oct 27 '15 at 19:22
  • 2
    \$\begingroup\$ I think the wording here is hard to digest. Let me say if I've understood right: You have a m*n grid of values, and a legal move consists of moving from a cell in the grid to another cell in the same row or column that has a strictly lower value. What is the minimum size r of a subset S of cells such that union of all length-r paths with start points in S covers the whole grid? \$\endgroup\$ – xnor Oct 27 '15 at 19:41
  • \$\begingroup\$ @xnor You're almost correct. Only thing that you missed out is that each path starts at a red cell, makes less than or equal to k turns and terminates. And every cell must be reachable by such a path. \$\endgroup\$ – ghosts_in_the_code Oct 28 '15 at 10:40