gistfile1.txt

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int T, n,m;
    int** influence = new int*[100];
    int*** dp = new int**[100];

    for (int i=0;i<100;i++)
    {
        influence[i] = new int[100];
        dp[i] = new int*[100];
        for (int j=0;j<100;j++)
        {
            dp[i][j] = new int[2];
        }
    }

    cin >> T;



    for(int t=0;t<T;t++)
    {
        cin >> n >> m;
        string* mapp = new string[n];

        // read map
        for (int n1=0;n1<n;n1++)
        {
            cin >> mapp[n1];
        }

        // initialisation
        for (int n1=0;n1<n;n1++)
        {
            for (int m1=0;m1<m;m1++)
            {
                influence[n1][m1] = 0;
                dp[n1][m1][0] = 0;
                dp[n1][m1][1] = 0;
            }
        }

        // create influence map
        for (int n1=0;n1<n;n1++)
        {
            for (int m1=0;m1<m;m1++)
            {
                if (mapp[n1].at(m1) == '1')
                {
                    influence[n1][m1] += 1;
                    if (m1-1 >= 0) influence[n1][m1-1]+=1;
                    if (n1-1 >= 0) influence[n1-1][m1]+=1;
                    if (m1+1 <  m) influence[n1][m1+1]+=1;
                    if (n1+1 <  n) influence[n1+1][m1]+=1;
                }
            }
        }

        // run dp
        int x,y;
        for (y=0;y<n;y++)
        {
            for (x=0;x<m;x++)
            {
                int fromleft,fromtop;
                dp[y][x][0] += influence[y][x];
                dp[y][x][1] += influence[y][x];

                if (x-1 >= 0)
                {
                    fromleft = min(dp[y][x-1][0], (y-1>=0)? (dp[y][x-1][1]-((mapp[y-1].at(x) == '1')?1:0)) : dp[y][x-1][1]);
                    if (mapp[y].at(x)=='1') fromleft -= 1;
                    if (mapp[y].at(x-1)=='1') fromleft -= 1;
                }
                if (y-1 >= 0)
                {
                    fromtop = min(dp[y-1][x][1], (x-1 >= 0) ? dp[y-1][x][0]-(((mapp[y].at(x-1)=='1')?1:0)) :  dp[y-1][x][0]);
                    if (mapp[y].at(x)=='1') fromtop -= 1;
                    if (mapp[y-1].at(x)=='1') fromtop -= 1;
                }

                if (x-1 < 0 and y-1 < 0)
                {


                } else if (x-1 < 0) {
                    dp[y][x][0] += fromtop;
                    dp[y][x][1] += fromtop;
                } else if (y-1 < 0) {
                    dp[y][x][0] += fromleft;
                    dp[y][x][1] += fromleft;
                } else {
                    dp[y][x][0] += fromleft;
                    dp[y][x][1] += fromtop;
                }
            }
        }
        cout << min(dp[y-1][x-1][0], dp[y-1][x-1][1])<<endl;
    }

    return 0;
}