Алгоритм проверки специального шаблона матрицы

Question

Я борюсь за эту проблему.

Алгоритм проверяет специальный шаблон матрицы, если он соответствует или не соответствует указанным значениям. Максимальный размерный размер равен 20x20.

Специальный шаблон: некоторый термин должен быть суммой или продуктом соседних ячеек. Суммы и клетки продуктов следуют друг за другом с помощью одной свободной клетки. Для строки Нечетные строки начинается с свободных ячеек, а для четной последовательности строк начинается с ячейки Sum или Product.

Пустого представление 3х4 матрицы (+ символ показать это сумма соседей, х символы показывает, что продукт соседей):

[][+][] 
[+][][x] 
[][x][] 
[x][][+] 

Приемлемый матрица 3х4:

[1][6][2] 
[9][3][8] 
[3][54][3] 
[5][2][6] 

Answer 1

#include <stdio.h> 
#include <memory.h> 

#define MAX_DIMENSION 20 

int dump_matrix(int m[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy) 
{ 
    int i, j; 
    printf(" "); 
    for(i = 0; i < dx; ++i) 
     printf("%4d ", i); 
    printf("\n "); 
    for(i = 0; i < dx; ++i) 
     printf("-----"); 
    printf("\n"); 
    for(j = 0; j < dy; ++j) 
    { 
     printf("%2d| ", j); 
     for(i = 0; i < dx; ++i) 
     { 
      printf("%4d ", m[i][j]); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
} 

int dump_matrix_check(char c[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy) 
{ 
    int i, j; 
    printf(" "); 
    for(i = 0; i < dx; ++i) 
     printf("%2d ", i); 
    printf("\n "); 
    for(i = 0; i < dx; ++i) 
     printf("---"); 
    printf("\n"); 
    for(j = 0; j < dy; ++j) 
    { 
     printf("%2d| ", j); 
     for(i = 0; i < dx; ++i) 
     { 
      printf("%c ", c[i][j]); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
} 

int test_matrix(int m[MAX_DIMENSION][MAX_DIMENSION], char c[MAX_DIMENSION][MAX_DIMENSION], int dx, int dy) 
{ 
    /* Test matrix. */ 
    int is_special = 1; /* Assume special unless we find a fail case. */ 
    int i, j; 
    dump_matrix(m, dx, dy); 
    for(i = 0; i < dx; ++i) 
    { 
     for(j = 0; j < dy; ++j) 
     { 
      int sum = (i ? m[i - 1][j] : 0) + (j ? m[i][j - 1] : 0) + ((i < dx - 1) ? m[i + 1][j] : 0) + ((j < dy - 1) ? m[i][j + 1] : 0); 
      int product = (i ? m[i - 1][j] : 1) * (j ? m[i][j - 1] : 1) * ((i < dx - 1) ? m[i + 1][j] : 1) * ((j < dy - 1) ? m[i][j + 1] : 1); 
      c[i][j] = (sum == m[i][j]) ? '+' : ((product == m[i][j]) ? '*' : ' ');  
      if((((m[i][j] == sum) || (m[i][j] == product)) ? 1 : 0) != (i + j) % 2) 
      { 
       /* Optionally, you can return 0 if you do not want to check the rest of the matrix */ 
       is_special = 0; 
      } 
      /* If you prefer the more readable long view: 
      if(i + j % 2) 
      { 
       // Check to make sure it is a free cell 
       if((m[i][j] == sum) || (m[i][j] == product)) 
        is_special = 0; 
      } 
      else 
      { 
       // Check to make sure it is a sum or product cell 
       if((m[i][j] != sum) && (m[i][j] != product)) 
        is_special = 0; 
      } 
      */ 
     } 
    } 
    dump_matrix_check(c, dx, dy); 

    return is_special; 
} 

int main(int argc, char ** argv) 
{ 
    int i, j; 
    int dx, dy; 
    char c[MAX_DIMENSION][MAX_DIMENSION]; 
    int m[MAX_DIMENSION][MAX_DIMENSION]; 

    /* Read in the values of the matrix */ 
    memset(&c, sizeof(char) * MAX_DIMENSION * MAX_DIMENSION, 0); 
    memset(&m, sizeof(int) * MAX_DIMENSION * MAX_DIMENSION, 0); 
    dx = 3, dy = 4; 
    m[0][0] = 1; m[1][0] = 6; m[2][0] = 2; 
    m[0][1] = 9; m[1][1] = 3; m[2][1] = 8; 
    m[0][2] = 3; m[1][2] = 54; m[2][2] = 3; 
    m[0][3] = 5; m[1][3] = 2; m[2][3] = 6; 

    /* Test matrix. */ 
    int is_special; 

    is_special = test_matrix(m, c, dx, dy); 
    printf("Matrix is %sspecial\n\n\n", (is_special ? "" : "not ")); 

    m[0][0] = 1; m[1][0] = -6; m[2][0] = 2; 
    m[0][1] = 9; m[1][1] = 3; m[2][1] = 8; 
    m[0][2] = 3; m[1][2] = 54; m[2][2] = 3; 
    m[0][3] = 5; m[1][3] = 2; m[2][3] = 6; 

    is_special = test_matrix(m, c, dx, dy); 
    printf("Matrix is %sspecial\n\n\n", (is_special ? "" : "not ")); 

    return 0; 
} 

Производит:

 0 1 2 
    --------------- 
0| 1 6 2 
1| 9 3 8 
2| 3 54 3 
3| 5 2 6 

    0 1 2 
    --------- 
0| +  
1| *  + 
2| *  
3| +  * 

Matrix is special 


     0 1 2 
    --------------- 
0| 1 -6 2 
1| 9 3 8 
2| 3 54 3 
3| 5 2 6 

    0 1 2 
    --------- 
0|  + 
1| *  + 
2| *  
3| +  * 

Matrix is not special 

Answer 2

Я возможно ошибочно, но что-то вроде этого должно работать: (псевдокод)

for each row 
    if row is odd 
     for all even col 
      check if m[row][col] sum or product of (m[row-1][col], m[row+1][col], m[row][col-1], m[row][col+1]) 
    if row is even 
     for all odd col 
      check if m[row][col] sum or product of (m[row-1][col], m[row+1][col], m[row][col-1], m[row][col+1]) 

Если какая-либо проверка не удалась, и вернуть false.

Просто добавьте некоторую логику для проверки строк/цв +/- 1, чтобы избежать Segfault, и это должно быть в порядке