Why didn't the pointer point at the right address?

Question

The pointer didn't point at the right place in the matrix. I would like to ask why. The following is the description of the question I've been working on, which is from JudgeGirl.

Description Write a program to compute the number of ways to go from the lower left corner of a matrix to upper right corner. The matrix has r rows and c columns. You can only move one cell to another cell, and only to the right or to the top. Also there are obstacles in the matrix and you cannot go into any cell that is obstacle . Please compute the number of ways you can go. Note that you are strongly suggested to think in "recursion" to solve this problem.

Limits Both r and c are no more than 12 .

Input Format There are r+1 lines in the input. The first line has r and c The next r lines have the status of the matrix. A 1 indicates a cell you can go through, and a 0 is an obstacle. Both the lower left and upper right corners are 1's.

Here's my code, and it turns out that the pointer doesn't point at the right address:

#include <stdio.h>
#include <assert.h>

void count(int x, int y, int r, int c, int *ptr, int *ways){
    if((*ptr==0)||(x>(c-1))||(y<0)){
        return;
    }else{
        //printf("(%d, %d) %d", x, y, *matrix);
    }

    if((x==(c-1))||(y==0)){
        *ways += 1;
        return;
    }
    
    count(x+1, y, r, c, &(*(ptr+1)), &(*ways));
    count(x, y-1, r, c, &(*(ptr-c)), &(*ways));
    
    return;

}

int main(){

    int r, c; //y:r x:c
    scanf("%d %d", &r, &c);
    assert((r<=12)&&(c<=12));
    int matrix[c][r];
    
    for(int j=0; j<r; j++){
        for(int i=0; i<c; i++){
            scanf("%d", &matrix[i][j]);
            //printf("%d ", matrix[i][j]);
        }
        //printf("\n");
    }
    
    int ways = 0;
    count(0, r-1, r, c, &matrix[0][r-1], &ways); //from(0,r-1) to (c-1,0)
    
    printf("%d", ways);
    
    return 0;

}

Answer 1

You create an array int matrix[c][r]; then form a pointer to one of the elements &matrix[0][r-1]. This is undefined behavior if r == 0. It is valid to form the address one past the end of the array but you cannot dereference that address (6.5.6, 9).

Within count() you then manipulate the pointer ptr as it was a 1d array which is also undefined behavior. Specifically, your row and column index values must be within the 2d array bounds when they are dereferenced.

1. It's a specification defect that the minimum bounds of r and c are not specified. Arrays cannot be zero sized (6.7.6.2) so I require r > 0 and c > 0. As an aside the problem description tells you that the size of the array is named r and c, if not, I would use rows and cols. Then use r and c as the index variables.

2. Multidimensional arrays are stored in row-major order (6.5.2.1) so you want major[r][c] and not the other way around.

3. Always check the return value of scanf() otherwise you may be operating on uninitialized data.

4. Pass the array to in as a variable length array (VLA) for the 2d array. Making it const to communicate that it's a read-only in count().

5. Return the count instead of using the ways out parameter.

6. Using unsigned types when appropriate.

#include <stdint.h>
#include <stdio.h>

uint32_t count(uint8_t row, uint8_t col, uint8_t r, uint8_t c, const uint8_t matrix[r][c]) {
    if(!matrix[row][col])
        return 0;
    if(row == r - 1 && !col)
        return 1;
    return (row < c - 1 ? count(row+1, col, r, c, matrix) : 0) +
        (col ? count(row, col-1, r, c, matrix) : 0);
}

int main(void) {
    uint8_t r;
    uint8_t c;
    if(scanf("%hhu %hhu", &r, &c) != 2) {
        printf("scanf failed\n");
        return 1;
    }
    if(!r || r > 12 || !c || c > 12) {
        printf("r or c out or range\n");
        return 1;
    }
    uint8_t matrix[r][c];
    for(int row=0; row<r; row++)
        for(int col=0; col<c; col++)
            if(scanf("%hhu", &matrix[row][col]) != 1) {
                printf("scanf failed\n");
                return 1;
            }
    printf("%u\n", count(0, r-1, r, c, matrix));
}

example runs:

2 2
1 1
1 1
2

2 2
1 1
1 0
1

Answer 2

I'd go for Allan's solution. However, staying close to your original code, here are the changes I'd do. I've commented on the changes in the code:

#include <assert.h>
#include <stdio.h>

// use y,x (or x,y) consistantly.
// if you use rows,columns, also use y,x
//
// Make ptr a pointer to an int[c] using int `ptr[][c]` or `int ptr[r][c]`:
void count(int y, int x, int r, int c, int ptr[r][c], int *ways) {
     // check bounds _before_ dereferencing the pointer:
    if ((x >= c) || (y < 0) || (ptr[y][x] == 0) ) { // x >= c instead of x > (c-1)
        return;
    }

    if ((x == (c - 1)) || (y == 0)) {
        *ways += 1;
        return;
    }

    count(y, x + 1, r, c, ptr, ways); // &(*ways) is the same as just ways
    count(y - 1, x, r, c, ptr, ways);

    return;
}

int main() {
    int r, c;  // y:r x:c
    if (scanf("%d %d", &r, &c) != 2 || r < 1 || c < 1) return 1;
    assert((r <= 12) && (c <= 12));
    int matrix[r][c]; // swapped row and col

    for (int j = 0; j < r; j++) {
        for (int i = 0; i < c; i++) {
            // you swapped i and j here:
            if(scanf("%d", &matrix[j][i]) != 1) return 1;
        }
    }

    int ways = 0;
    count(r - 1, 0, r, c, matrix, &ways);  // from(0,r-1) to (c-1,0)

    printf("%d", ways);
}

Answer 3

In C, a 2D array is stored as a 2d continuous array ( refer https://i.stack.imgur.com/70Ezz.jpg, Are C multidimensional arrays contiguous without holes? ), but using pointer arithmetic would not work as you expect. Instead you can use 'i-j' to access 2d array as a normal array[i][j]. And in the base it is best to check if matrix[i][j] == 0. Hope this helps.