LightOJ1004

#include<bits/stdc++.h>

using namespace std;

int Map[106][106];

int Vis[106][106];

int Num[106][106];

int T;

const int step[2][2] = {1,0,0,1};

void Init()

{

    memset(Map,0,sizeof(Map));

    memset(Vis,0,sizeof(Vis));

    memset(Num,0,sizeof(Num));

}

struct Node {

    int x, y;

    Node(int _x = 0, int _y = 0) :\

    x(_x), y(_y) {}

};

int BFS(int n)

{

    Num[0][0] = Map[0][0];

    Node Begin(0,0);

    queue<Node> Q;

    Q.push(Begin);

    while(!Q.empty())

    {

        Node c = Q.front();

        Q.pop();

        int s = Num[c.x][c.y];

        for(int i = 0; i < 2; ++i)

        {

            int xx = c.x + step[i][0];

            int yy = c.y + step[i][1];

            //cout << Num[xx] << "  " << Num[yy] <<endl;

            if(xx < 0 || xx >= n || yy < 0 || yy >= n) continue;

            if(s + Map[xx][yy] > Num[xx][yy])

            {

                //cout << 1 <<endl;

                Num[xx][yy] = s+Map[xx][yy];

                Q.push(Node(xx,yy));

            }

        }

    }

    return Num[n-1][n-1];

}

void RedMap(int n)

{

    int bx = 0, by = 0;

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

    {

        int xx = bx, yy = by;

        for(int j = 1; j <= i; ++j)

        {

            cin >> Map[xx][yy];

            //cout << xx<< "  " << yy << endl;

            xx--, yy++;

        }

        bx++;

    }

    bx --, by ++;

    for(int i = 1; i <= n-1; ++i)

    {

        int xx = bx, yy = by;

        for(int j = 1; j <= n-i; ++j)

        {

            cin >> Map[xx][yy];

            //cout << xx<<"  " << yy << endl;

            xx--, yy++;

        }

        by++;

    }

}

int main()

{

    int t, n;

    cin >> t;

    for(int kase = 1; kase <= t; ++kase)

    {

        cin >> n;

        Init();

        RedMap(n);

        printf("Case %d: %d\n",kase, BFS(n));

        /*for(int i = 0; i < n; ++i)

        {

            for(int j = 0; j < n; ++j)

                cout << Num[i][j] << " ";

            cout << endl;

        }*/

    }

}