c - 在二维矩阵(水平、垂直、对角线)中查找回文

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 6 年前。

Improve this question

我从一本编程难题书中得到了这个问题陈述。我能够找出水平回文，但前提是整行都是回文。

我怎样才能实现这个目标？另外如何获得对角回文？
伪代码也可以，我只需要其背后的基本逻辑。剩下的事情我来完成。谢谢。

Answer 1

查找水平回文的技巧是获取整行，然后将其拆分为不同的字符串。完成后，您需要检查该字符串是否是回文。对于垂直字符串，您需要对列执行相同的操作。

现在对于对角线，你需要从边缘的一个点开始，然后沿对角线向前移动(+[1][1])到右下角，直到到达终点。现在继续对每条边的每个战术点进行操作，这将帮助您获得所有对角线字符串，接下来您需要做的就是分割这些字符串并检查每个短字符串是否是回文。

这很可能属于动态规划。虽然我很困惑，但它也可能会受到贪婪的方法的影响。我会和我的教授确认一次。

这是我在尝试解决同样的问题时所做的代码 -

#define PALLEN 2

#include <stdio.h>
#include <string.h>

int a[10][10];

/*int a[5][5] = {
        { 1, 2, 1, 3, 5 } ,
        { 4, 5, 6, 7, 4 } ,
        { 4, 5, 5, 4, 1 } ,
        { 1, 9, 2, 1, 4 } ,
        { 1, 9, 4, 1, 5 }
};*/
int n=0;

void checkPalindrome(char*);
void diagonalPal();
void stringSpliter(char*);

int main() {

    int i, j, k, l, x;
    int c = 0;
    int jmp;
    int ptr = 0;

    int diag;

    char recycler[20];
    char diaglist[25];
    char revdiaglist[25];

    system("cls");

    printf("\nEnter the dimension (n) of this square matrix i.e. (n*n) - ");
    scanf("%d", &n);

    printf("\nNow enter the elements for this %d*%d matrix - ", n,n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d", &a[i][j]);



    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            printf("-%d-", a[i][j]);
        }
        printf("\n");
    }


    printf("\nHorizontal Palindromes");
    for (i = 0; i < n; i++) {
        for (j = n-1, k = PALLEN; j > 0; j--, k++) {
            while (c < j) {
                jmp = c;
                memset(recycler, 0, 20);
                ptr = 0;
                for (l = 0; l < k; l++) {
                    recycler[ptr] = a[i][jmp]; //0,0 -- 0,1
                    ptr++;
                    jmp++;
                }
                checkPalindrome(recycler);
                c++;
            }
            c = 0;
        }

    }

    printf("\n\nVertical Palindromes");
    for (i = 0; i < n; i++) {
        for (j = n-1, k = PALLEN; j > 0; j--, k++) {
            while (c < j) {
                jmp = c;
                memset(recycler, 0, 20);
                ptr = 0;
                for (l = 0; l < k; l++) {
                    recycler[ptr] = a[jmp][i]; //0,0-- 1,0
                    ptr++;
                    jmp++;
                }
                checkPalindrome(recycler);
                c++;
            }
            c = 0;
        }
    }


    printf("\n\nDiagonal Palindromes");
    diagonalPal();

}

void stringSpliter(char *a){

    int i,j,k,ptr,jmp,c=0,l;
    int len;
    len = strlen(a);

    char recycler[20];

    for (j = len-1, k = PALLEN; j > 0; j--, k++) {
        while (c < j) {
            jmp = c;
            memset(recycler, 0, 20);
            ptr = 0;
            for (l = 0; l < k; l++) {
                recycler[ptr] = a[jmp]; //0,0 -- 0,1
                ptr++;
                jmp++;
            }
            checkPalindrome(recycler);
            c++;
        }
        c = 0;
    }

}

void diagonalPal(){

    int i, x=0, j, k, ptr=0;
    char diagrecycler[20];

    for(i = 0; i < n; i++){

        memset(diagrecycler, 0, 25);
        ptr = 0;
        for(j = i, k = 0; j < n, k < n; j++, k++){
            diagrecycler[ptr++] = a[j][k];
        }
        stringSpliter(diagrecycler);
    }

    for(i = 1; i < n; i++){

        memset(diagrecycler, 0, 25);
        ptr = 0;
        for(j = 0, k = i; j < n, k < n ;j++, k++){
            diagrecycler[ptr++] = a[j][k];
        }

        stringSpliter(diagrecycler);
    }

}


void checkPalindrome(char *string){

    int isPalindrome = 1, i=0;
    char rev[20];

    strcpy(rev, string);
    strrev(rev);

    isPalindrome = strcmp(rev, string);

    if(isPalindrome == 0){
        printf("\n");
        while(string[i]!='\0')  printf("%d", string[i++]);
    }

}

// Output
/*Enter the dimension (n) of this square matrix i.e. (n*n) - 4

Now enter the elements for this 4*4 matrix - 1 2 3 4
5 2 1 6
8 1 1 8
9 5 3 2
-1--2--3--4-
-5--2--1--6-
-8--1--1--8-
-9--5--3--2-

Horizontal Palindromes
11
8118

Vertical Palindromes
22
11
3113

Diagonal Palindromes
121
212
G:\Code snippets\C programmes>*/