Chess-like matrix in c

Question

I have a n x m matrix containing alternative black and white cells(like a chessboard) and a constant c which is 0 if the bottom right corner is black, and 1, if it is white.

And I am having trouble figuring out how many 8×8 different boards with a white bottom right corner can be found on a n x m matrix.

I was thinking I should start with the bottom right corner and check its color. If it is white, then I have a good case (n>8 && m>8), but i don't know how to impose the 8 x 8 condition.

possible duplicate of [Creating 2D array in single malloc() call](http://stackoverflow.com/questions/18460979/creating-2d-array-in-single-malloc-call); see also [this](http://stackoverflow.com/a/18461105/841108) & [this](http://stackoverflow.com/a/18461105/841108) answers. — Basile Starynkevitch, Sep 19 '13 at 16:35
I don't see how this is a duplicate of that question. I am having troubles implementing the algorithm for determining the number of 8 x 8 boards with white bottom right corner contained in an n x m matrix — user2791841, Sep 19 '13 at 16:42
Simple question, since you only have black and white, if it s like a chessboard, how can you have more than two cases? As long as the array have similar height and width, wich is pair, there is only two combination? — DrakaSAN, Sep 19 '13 at 16:48
@user2791841 Can you please give some sample input output? What is the output for n = 9 and m = 9? There can be 4 possible 8*8 chessboards, and I guess the ans is 2? — Rafi Kamal, Sep 19 '13 at 16:48
@RafiKamal agreed, this doesn't seem like a programming problem at all to me. — TooTone, Sep 19 '13 at 16:49
@user2791841 If I understand the problem right, it's an backtracking problem — Rafi Kamal, Sep 19 '13 at 16:53
@RafiKamal: yes, you are right. with the outuput for n=9 and m=9 — user2791841, Sep 19 '13 at 16:53
@DrakaSAN: the n x m array is not necessarily square, so there can be more than 2 cases. — user2791841, Sep 19 '13 at 17:01
@user2791841: I didn t understoud they weren t necessarily square, thanks you — DrakaSAN, Sep 20 '13 at 07:46

score 2 · Answer 1 · answered Sep 19 '13 at 17:13

If the bottom right corner of the nxm board is white, then there are ceiling( (n-7)(m-7)/2 ) possible chessboards.

If the bottom right corner of the nxm board is black, then there are floor( (n-7)(m-7)/2 ) possible chessboards.

The way to see this is to look at where the upper-left corner of the chessboard can be. It is limited to the upper-left (n-7)x(m-7) subgrid in the nxm grid. Since the upper-left corner of the chessboard is always white, the question reduces to how many white squares are there in this (n-7)x(m-7) subgrid.

score 1 · Answer 2 · answered Sep 19 '13 at 17:13

Let the bottom right index is (0, 0) and the top left index is (N, M). Now, the bottom right index (i, j) of each of the 8*8 squares should maintain the following property:

i <= N - 8

j <= M - 8

There are (N - 8 + 1) * (M - 8 + 1) such squares. How many of them has bottom right corner marked white? If you draw some chessboards in paper, you will find the answer is

ceil((N - 7) * (M - 7) / 2)

Chess-like matrix in c

2 Answers2