c - 检查矩阵特殊模式的算法

Question

我正在为这个问题苦苦挣扎。

算法会根据我们输入的值检查一个特殊的矩阵模式是否适合。最大尺寸限制为20x20。

特殊模式:某些项必须是相邻单元格的总和或乘积。 Sum 和 product 单元格彼此跟随一个空闲单元格。对于奇数行，序列以空闲单元开始，对于偶数行，序列以 Sum 或 Product 单元开始。

3x4 矩阵的空表示(+ 符号表示它是邻居的总和，x 符号表示它是邻居的乘积):

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

可接受的 3x4 矩阵:

[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