As I often say, try doing it yourself on paper. Write out (with the computer's help if necessary) 16 random numbers and see what the count would come to for varying values of k. This isn't a simple task and you're not going to solve it by starting to type out some code; you need to work out an algorithm first.

Once you've done it a few times on paper you should start getting the hang of it and you can then start thinking about an algorithm for the computer to follow.

So let's say we have
Code:
14 27  6 13
15  8  4  2
 2  7 12 15
 9 23  7  1

k=10
the answer would be 4 (assuming the 12 and 23 aren't neighbours, so 3 if diagonal neighbours count), but how would you work that out on paper?

Hint: if I were tasked with solving this, I'd use a second array with the same dimensions as the first.