#include <stdio.h>
#include <stdlib.h>

#define MAXN    10

typedef struct
{
        int row, col;
        int val;
}RcdType;

int n, length;
int map[MAXN+2][MAXN+2];
RcdType rcd[MAXN*MAXN];
int decv[MAXN*MAXN];
int decx[MAXN*MAXN];

int Comp(const void *p1, const void *p2)       
{
        RcdType *e1 = (RcdType *)p1;
        RcdType *e2 = (RcdType *)p2;
        if (e1->val > e2->val)
                return -1;
        else if (e1->val < e2->val)
                return 1;
        else
                return 0;                     
}

int Work()
{
        int i, j, k, r, c;
        int res = rcd[0].val, idx = 0;
        int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        qsort((void *)rcd, length, sizeof(RcdType), Comp);
        for (i=0; i<=n+1; i++)
                map[0][i] = map[i][0] = map[n+1][i] = map[i][n+1] = -1;
        for (i=0; i<length; i++)
        map[rcd[i].row][rcd[i].col] = i;

        for (i=length-1; i>=0; i--)
        {
                decv[i] = rcd[i].val;
                decx[i] = -1;
                for (j=0; j<4; j++)
                {
                        r = rcd[i].row+d[j][0];
                        c = rcd[i].col+d[j][1];
                        k = map[r][c];
                        if (k!=-1 && rcd[i].val>rcd[k].val)
                                if (decv[i] < rcd[i].val+decv[k])
                                {
                                        decv[i] = rcd[i].val+decv[k];
                                        decx[i] = k;
                                }
                }
                if (res < decv[i])
                {
                        res = decv[i];
                        idx = i;
                }
        }
        return idx;
}

void Display(int idx)
{
        int i = idx, cnt = 0;
        printf("max sequence sum = %d\n", decv[idx]);
        printf("one sequence is :");
        while (i != -1)
        {
                printf(" %d", rcd[i].val);
                i = decx[i];
                cnt++;
        }
        printf("\nsequence length = %d\n\n", cnt);
}

int ReadData()
{
        int i, j, k, v;
        if (scanf("%d", &n) == EOF)
                return 0;
        length = n*n;
        for (i=1; i<=n; i++)
                for (j=1; j<=n; j++)
                {
                        scanf("%d", &v);
            k = (i-1)*n+j-1;
                        rcd[k].row = i;
                        rcd[k].col = j;
                        rcd[k].val = v;
                }
        return 1;
}

int main()
{
        int idx;
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        
        while (ReadData())
        {
                idx = Work();
                Display(idx);
        }

        return 0;
}

评论