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\$

closed as unclear what you're asking by Mego, AdmBorkBork, ETHproductions, Downgoat, GamrCorps Oct 27 '15 at 22:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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