SRM 513 D2 1000 CutTheNumbers

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long LL;
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define REP(k,a) for(int k=0; k < (a); ++k)


class CutTheNumbers {
    vector<vector<int> > mBoard;
    int calc(int x1, int x2, int y1, int y2)
    {
        int res=0,res2=0,tmp=0;
        FOR(i,x1,x2)
        {
            tmp=0;
            FOR(j,y1,y2)
            {
                tmp*=10;
                tmp+=mBoard[i][j];
            }
            res+=tmp;
        }
        FOR(j,y1,y2)
        {
            tmp=0;
            FOR(i,x1,x2)
            {
                tmp*=10;
                tmp+=mBoard[i][j];
            }
            res2+=tmp;
        }
        res=max(res,res2);
        FOR(i,x1+1,x2)
            res=max(res,calc(x1,i,y1,y2)+calc(i,x2,y1,y2));
        FOR(i,y1+1,y2)
            res=max(res,calc(x1,x2,y1,i)+calc(x1,x2,i,y2));
        return res;
    }
public:
    int maximumSum(vector <string> board) {
        int n=board.size();
        int m=board[0].size();
        mBoard.resize(n,vector<int> (m));
        REP(i,n)
        REP(j,m)
        {
            mBoard[i][j]=board[i][j]-'0';
        }
        return calc(0,n,0,m);
    }

};