程序代码：

/* 
一条贪吃的蛇在一个n*m的网格中游走，它只能从一个方格走向另一个相邻的方格，
这里相邻的意思是两个方格有公共边。每个方格可以看作是一个房间，其中一些是空的，一些存放有苹果。
贪吃的蛇根本不进入空的房间，而进入有苹果的房间后就可以带走所有苹果使房间成为空的。
蛇从一个指定的房间出发，最终回到它的家，把一路带来的苹果存储到家中，当然，它希望带来的苹果最多。
请编写程序，输入有整数n和m，及n*m的一个矩阵，
矩阵元素数值中有一个是 -1，表示蛇的出发位置，有一个是 -2，表示蛇的家的位置，
其余数值是非负整数，0表示房间为空，非零整数表示苹果的数目。
输出蛇选择的游走路径和获得的最多的苹果数目。例如输入4*4矩阵：

 7   0   4  18
4   0   1   1
15   7  11   -1

 0  12  -2   0
则应输出 (2, 3), (1, 3), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (3, 2),

 带回苹果数为1+18+4+1+11+7+12 = 54。（本题为2011年ACM大赛题目）。

 （可查阅：吕国英，任瑞征等编著，算法设计与分析（第2版），清华大学出版社，2009年1月，第200-202页。
提示：这是一个利用回溯算法的迷宫搜索类型问题，可参考类似问题的已有解法。
*/
#include<stdio.h>
#define Maxlen 30        //矩阵最大行列数
#define Maxsize 100      //栈最大存储数
typedef struct
{
    int row;                     //矩阵行数
    int column;                  //矩阵列数
    int grid[Maxlen][Maxlen];    //矩阵当前元素
    char lattice[Maxlen][Maxlen];//保存单元格状态
}MatrixType;
typedef struct
{
    int row;             //行号
    int column;          //列号
}Coordinate;             //坐标
typedef struct 
{
    int ord;              //当前位置序号
    Coordinate seat;      //当前坐标
    int f;                //下个坐标的方向
}MatrixNode;              
typedef struct
{
    MatrixNode store[Maxsize];     //储存坐标 
    int top;
}Stack;                       //栈

Stack InitStack( Stack S )                 //构建空栈
{
    S.top = -1;
    return S;
}

int EmptyStack( Stack S )                 //判断栈空
{
    if( S.top == -1 )
        return 1;
    else
        return 0;
}


void Push( Stack S, MatrixNode e )         //插入新的栈顶元素
{
    if(S.top == Maxsize-1)
    {
        printf("栈满\n");
        exit(0);
    }
    S.top++;
    S.store[S.top]=e;
}


int Pop( Stack S, MatrixNode e )        //删除栈顶元素
{
    if( S.top==-1 )
    {
        printf("栈空\n");
        exit(0);
    }
    else
    {
        e=S.store[S.top];
        S.top--;
        return 1;
    }
    return 0;
}


int DeleteStack( Stack S )              //清空栈
{
    S.top=-1;
    return 1;
}





int MatrixInit( MatrixType matrix )            //初始化矩阵
{
    int i, j;
    printf("请输入矩阵的行数与列数: ");
    scanf("%d%d",&matrix.row,&matrix.column);  //矩阵行和列数
    for(i=0; i<=matrix.column+1; i++)          //设置行外墙
    {
        matrix.grid[0][i]=0;
        matrix.grid[matrix.row+1][i]=0;
        matrix.lattice[0][i]='1';
        matrix.lattice[matrix.row+1][i]='1';
    }
    for(i=0; i<=matrix.row+1; i++)              //设置列外墙
    {
        matrix.grid[i][0]=0;
        matrix.grid[i][matrix.column+1]=0;
        matrix.lattice[i][0]='1';
        matrix.lattice[i][matrix.column+1]='1';
    }
    printf("输入矩阵%d*%d元素，入口-1与出口-2\n",matrix.row,matrix.column);
    for(i=1; i<=matrix.row; i++)                //输入矩阵元素
    {    
        for(j=1; j<=matrix.column; j++)
        {
            scanf("%d",&matrix.grid[i][j]);
            matrix.lattice[i][j]='0';
        }
    }
    for(i=1; i<=matrix.row; i++)
    {
        for(j=1; j<=matrix.column; j++)
        {
            if(matrix.grid[i][j]==0)
                matrix.lattice[i][j]='1';
        }
    }
    return 1;
}


int Pass( MatrixType matrix, Coordinate p )     //判断指定坐标是否可通过
{
    if(matrix.lattice[p.row][p.column] == '0')
        return 1;
    else
        return 0;
}


int MakerPass( MatrixType matrix, Coordinate p )
{
    matrix.lattice[p.row][p.column]='2';     //2表示可通过
    return 1;
}


Coordinate NextCoord( Coordinate p, int i )
{
    switch(i)
    {
    case 1:
        p.column += 1;
        break;
    case 2:
        p.row += 1;
        break;
    case 3:
        p.column -= 1;
        break;
    case 4:
        p.row -= 1;
        break;
    default:
        exit(0);
    }
    return p;
}


int MakerNoPass( MatrixType matrix, Coordinate p )
{
    matrix.lattice[p.row][p.column]='3';
    return 1;
}

void PrintMatrix( MatrixType matrix )
{
    int i,j,a[Maxsize],k=0,sum=0;
    for(i=0; i<=matrix.row+1; i++)
    {
        for(j=0; j<=matrix.column+1; j++)
        {
            if(matrix.lattice[i][j]=='2')
            {
                printf("(%d,%d)\n",i,j);
                a[k]=matrix.grid[i][j];
                k++;
            }
        }
    }
    for(i=1;i<k-1;i++)
    {
        printf(" %d +",a[i]);
        sum+=a[i];
    }
    sum+=a[k-1];
    printf(" %d = %d \n",a[k-1],sum);
}



int MatrixPath( Stack S, MatrixType matrix, Coordinate start, Coordinate end )
{
    Coordinate p;                 //保存单元格的坐标
    int choosestep;               //选择方向，右下左上分别用1，2，3，4表示
    MatrixNode e;                 
    p=start;                      //指向入口坐标
    choosestep=1;                 //探索第一步
    do
    { 
        if( Pass( matrix, p ) )      //若指定位置可通过
        {
            MakerPass( matrix, p );  //标记能通过
            e.ord  =choosestep;      //保存步数
            e.seat =p;               //保存当前坐标
            e.f    =1;               //向右继续控测
            Push( S, e );           //入栈
            if( p.row == end.row && p.column == end.column )
            {
                DeleteStack( S );
                return 1;
            }
            else
            {
                p= NextCoord( p, 1 );    //向右探测
                choosestep++;            //继续向前加
            }
        }
        else
        {
            if( !EmptyStack( S ))    //若栈非空
            {
                Pop( S, e );
                while( e.f == 4 && !EmptyStack( S ) )
                {
                    MakerNoPass( matrix, e.seat );
                    Pop( S, e);
                }
                if( e.f < 4 )
                {
                    e.f++;             //改变探测方向
                    Push( S, e );
                    p= NextCoord( e.seat, e.f);
                }
            }
        }
    }while( !EmptyStack( S ) );
    DeleteStack( S );
    return 0;
}



void main()
{
    int i,j;
    Stack S;                       //定义栈
    MatrixType matrix;             //定义矩阵
    Coordinate start,end;          //定义开始与结束坐标
    InitStack(S);                  //初始化栈
    printf("创建矩阵\n");
    if( !MatrixInit(matrix) )      //初始化并创建矩阵
    {
        printf("创建矩阵出错\n");
        exit(0);
    }
    for(i=1; i<=matrix.row; i++)       //寻找矩阵的入口坐标
    {
        for(j=1; j<=matrix.column; j++)
        {
            if( matrix.grid[i][j]==-1 )
            {
                start.row=i;
                start.column=j;
                break;
            }
            else
            {
                printf("矩阵没有入口,创建矩阵出错\n");
                exit(0);
            }
        }
    }
    for(i=1; i<=matrix.row; i++)        //寻找矩阵的出口坐标
    {
        for(j=1; j<=matrix.column; j++)
        {
            if( matrix.grid[i][j]==-2 )
            {
                end.row=i;
                end.column=j;
                break;
            }
            else
            {
                printf("矩阵没有出口,创建矩阵出错\n");
                exit(0);
            }
        }
    }
    if(!MatrixPath( S, matrix, start, end ))
        printf("没有路径能从入口到达出口，创建矩阵出错\n");
    else
        PrintMatrix( matrix );
}