Hey I'm trying to build a function that checks if a N*N matrix has at least two adjacent (up-down-left right) same numbers ( numbers go from 0 to h-1) and returns 1 if does, 0 if it doesn't. I wanted to first check along the rows if the upcoming element was the same, and than I did the same along the columns. However I have to be careful with the last elements since board[n][j] or board[i][n] don't exist. This is what I wrote, is there a faster way to solve this problem? Also, my solution is correct?

int check (game_t *p){
int i,j;
for (i=0;i<p->n;i  ){
      for (j=0;j<p->n-1;j  ){
               if(p->board[i][j]==p->board[i][j 1]) return 1;}}
for (j=0;j<p->n;j  ){
      for (i=0;i<p->n-1;i  ){
               if(p->board[i][j]==p->board[i 1][j]) return 1;}}
return 0;
}

The structure game is defined:

typedef struct game {
int h;
int n;
int ** board;
} game_t;

CodePudding user response：

A slight bit of restructuring. We can combine the row adjacency tests and the column adjacency tests into a single loop.

When checking a given row, we can compare against the previous value of the row. But, we can also check the value against the value below it in the next row.

We can do this in a single loop of the row values. So, we only need one set of nested for loops and not two.

We add a special loop at the end to check the final row [without a check for the next row].

Also, by adding some additional int * pointers to point to the rows being compared, we can simplify the board matrix indexing and eliminate some repetitive extra pointer/value fetches.

Here is the refactored code. It is annotated:

typedef struct game {
    int h;
    int n;
    int **board;
} game_t;

int
check(game_t *p)
{
    int n = p->n;
    int nm1 = n - 1;
    int yidx;
    int xidx;
    int xcur;
    int xprev;
    int *rowtop;
    int *rowbot;

    // check most rows
    yidx = 0;
    for (;  yidx < nm1;    yidx) {
        // point to current row of board
        rowtop = p->board[yidx];

        // point to next row of board
        rowbot = p->board[yidx   1];

        // get the "previous" value in the current row
        xprev = rowtop[0];

        // check all values in given row
        for (xidx = 1;  xidx < n;    xidx, xprev = xcur) {
            // get current value
            xcur = rowtop[xidx];

            // does it match the previous value in the row?
            if (xcur == xprev)
                return 1;

            // check current value against value just below it in the next row
            if (xcur == rowbot[xidx])
                return 1;
        }
    }

    // check last row
    rowtop = p->board[yidx];
    xprev = rowtop[0];
    for (xidx = 1;  xidx < n;    xidx, xprev = xcur) {
        xcur = rowtop[xidx];
        if (xcur == xprev)
            return 1;
    }

    return 0;
}