字节跳动20180512 编程题第5题
早上没做出来，大概写了一下，思路应该是正确的吧。。。

[编码题|20分] 贪吃蛇蛇小游戏

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++ 32768K，其他语言 65536K

题目描述

小Q最近迷上了一款叫“贪吃蛇蛇”的小游戏。平面上有个数字矩阵，每个单元都是一个整数，有正有负，最开始的时候小Q操纵一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数（注：最多只能改变一个节点）。问在小Q游戏过程中，他的蛇蛇最长长度可以到多少？

输入描述:

第一行两个整数n, m，表示地图有n行m列
接下来n行，每行m个整数T(i, j)表示地图中每个单元的值

输出描述:

一个整数，表示蛇最长的长度

示例1

输入

4 3
1 -4 10
3 -2 -1
2 -1 0
0 5 -2

输出

17

说明

将第一行第二列的-4改成4，然后从第二行的第一列进入地图，路线是3 -> 4(原-4) -> 10

备注:

数据范围
对于40%的数据 1 <= n, m <= 20
对于100%的数据 1 <= n, m <= 1000，-1000 <= T(i, j) <= 1000

#include <stdio.h>
#include <malloc.h>
#define NOMAGIC false
#define DOMAGIC true
#define MAXSIZE 1000



int fun(int w[MAXSIZE][MAXSIZE],const int rows,const int cols){

    bool mg1[MAXSIZE]={};
    bool mg2[MAXSIZE]={};

    int arr1[MAXSIZE]={0};
    int arr2[MAXSIZE]={0};

    int * last=arr1;
    int * current=arr2;

    bool * magiced=mg1;
    bool * lastMagiced=mg2;
    //初始化
    for(int i=0;i<rows+2;++i){
        magiced[i]=NOMAGIC;
        lastMagiced[i]=NOMAGIC;
        arr1[i]=0;
        arr2[i]=0;
    }

    for (int col=cols;col>0;--col){

        for(int i=1;i<=rows;++i){

            current[i]=0;
            magiced[i]=false;

            int weight=w[i][col];
            bool isMagiced=false;
            int lastIndex=-1;

            if(w[i][col]<0){

                //没有使用过魔法
                for(int k=i-1;k<i+2;++k){
                    //没使用过
                    if(lastMagiced[k]==NOMAGIC&&last[k]-w[i][col]>weight){
                        weight=last[k]-w[i][col];
                        isMagiced=true;                    //在当前节点使用超能力
                        lastIndex=k;
                    }
                }
            }

            for(int k=i-1;k<i+2;++k){                    
                if(last[k]+w[i][col]>weight){
                    weight=last[k]+w[i][col];
                    isMagiced=false;                    //使用超能力
                    lastIndex=k;
                }
            }
            //使用了魔法
            if(isMagiced){
                //设置一下,记录使用了魔法
                magiced[i]=DOMAGIC;
            }else{
                //包含了使用过超能力的点
                if(lastMagiced[lastIndex]){
                    magiced[i]=DOMAGIC;
                }
            }
            //最大值
            current[i]=weight;
        }

        int *tmp=last;
        last=current;
        current=tmp;    

        bool *mg=magiced;
        magiced=lastMagiced;
        lastMagiced=mg;
    }

    //在第一列找到最大值
    int max=0;
    for(int i=0;i<rows;++i){
        if(last[i]>max){
            max=last[i];
        }
    }
    return max;
}


int main(void){

    int n,m;
    scanf("%d %d",&n,&m);
    int (*arr)[MAXSIZE]  =(int (*)[MAXSIZE])malloc(MAXSIZE*MAXSIZE*sizeof(int));

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&arr[i][j]);
        }
    }

    int len=fun(arr,n,m);
    free(arr);

    printf("%d",len);

    return 0;
}