ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1325. Dirt

Why o(nm) get TL?
Posted by Felix_Mate 2 Aug 2016 15:34
#pragma comment(linker, "/STACK:50000000")
#include <stdio.h>
const int nmax= 505;
const int inf = nmax*nmax + 13;

char a[nmax][nmax];
int M1[nmax*nmax][3];
int d[nmax][nmax], k[nmax][nmax];
int n, m, i, j, xs, ys, xf, yf;

void BFS(int up, int down)
{
    int x, y;
    down++;
    if (down <= up)
    {
        x = M1[down][1];
        y = M1[down][2];
        if ((x - 1 >= 1) && (y - 1 >= 1) && (k[x - 1][y - 1] == inf) && (a[x - 1][y - 1] == a[x][y]) && (a[x - 1][y - 1] != '0'))
        {
            k[x - 1][y - 1] = k[x][y];
            up++;
            M1[up][1] = x - 1;
            M1[up][2] = y - 1;
        }
        if ((x - 1 >= 1) && (k[x - 1][y] == inf) && (a[x - 1][y] == a[x][y]) && (a[x - 1][y] != '0'))
        {
            k[x - 1][y] = k[x][y];
            up++;
            M1[up][1] = x - 1;
            M1[up][2] = y;
        }
        if ((x - 1 >= 1) && (y + 1 <= m) && (k[x - 1][y + 1] == inf) && (a[x - 1][y + 1] == a[x][y]) && (a[x - 1][y + 1] != '0'))
        {
            k[x - 1][y + 1] = k[x][y];
            up++;
            M1[up][1] = x - 1;
            M1[up][2] = y + 1;
        }
        if ((y - 1 >= 1) && (k[x][y - 1] == inf) && (a[x][y - 1] == a[x][y]) && (a[x][y - 1] != '0'))
        {
            k[x][y - 1] = k[x][y];
            up++;
            M1[up][1] = x;
            M1[up][2] = y - 1;
        }
        if ((y + 1 <= m) && (k[x][y + 1] == inf) && (a[x][y + 1] == a[x][y]) && (a[x][y + 1] != '0'))
        {
            k[x][y + 1] = k[x][y];
            up++;
            M1[up][1] = x;
            M1[up][2] = y + 1;
        }
        if ((x + 1 <= n) && (y - 1 >= 1) && (k[x + 1][y - 1] == inf) && (a[x + 1][y - 1] == a[x][y]) && (a[x + 1][y - 1] != '0'))
        {
            k[x + 1][y - 1] = k[x][y];
            up++;
            M1[up][1] = x + 1;
            M1[up][2] = y - 1;
        }
        if ((x + 1 <= n) && (k[x + 1][y] == inf) && (a[x + 1][y] == a[x][y]) && (a[x + 1][y] != '0'))
        {
            k[x + 1][y] = k[x][y];
            up++;
            M1[up][1] = x + 1;
            M1[up][2] = y;
        }
        if ((x + 1 <= n) && (y + 1 <= m) && (k[x + 1][y + 1] == inf) && (a[x + 1][y + 1] == a[x][y]) && (a[x + 1][y + 1] != '0'))
        {
            k[x + 1][y + 1] = k[x][y];
            up++;
            M1[up][1] = x + 1;
            M1[up][2] = y + 1;
        }
        BFS(up, down);

        if ((x - 1 >= 1) && (y - 1 >= 1) && (k[x - 1][y - 1] == inf) && (a[x - 1][y - 1] != a[x][y]) && (a[x - 1][y - 1] != '0'))
        {
            k[x - 1][y - 1] = k[x][y] + 1;
            up++;
            M1[up][1] = x - 1;
            M1[up][2] = y - 1;
        }
        if ((x - 1 >= 1) && (k[x - 1][y] == inf) && (a[x - 1][y] != a[x][y]) && (a[x - 1][y] != '0'))
        {
            k[x - 1][y] = k[x][y] + 1;
            up++;
            M1[up][1] = x - 1;
            M1[up][2] = y;
        }
        if ((x - 1 >= 1)&&(y + 1 <= m)&&(k[x - 1][ y + 1] == inf)&&(a[x - 1][ y + 1]!=a[x][ y])&&(a[x - 1][ y + 1]!='0'))
        {
            k[x - 1][ y + 1] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x - 1;
            M1[up][ 2] = y + 1;
        }
        if ((y - 1 >= 1)&&(k[x][ y - 1] == inf)&&(a[x][ y - 1]!=a[x][ y])&&(a[x][ y - 1]!='0'))
        {
            k[x][ y - 1] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x;
            M1[up][ 2] = y - 1;
        }
        if ((y + 1 <= m)&&(k[x][ y + 1] == inf)&&(a[x][ y + 1]!=a[x][ y])&&(a[x][ y + 1]!='0'))
        {
            k[x][ y + 1] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x;
            M1[up][ 2] = y + 1;
        }
        if ((x + 1 <= n)&&(y - 1 >= 1)&&(k[x + 1][ y - 1] == inf)&&(a[x + 1][ y - 1]!=a[x][ y])&&(a[x + 1][ y - 1]!='0'))
        {
            k[x + 1][ y - 1] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x + 1;
            M1[up][ 2] = y - 1;
        }
        if ((x + 1 <= n)&&(k[x + 1][ y] == inf)&&(a[x + 1][ y]!=a[x][ y])&&(a[x + 1][ y]!='0'))
        {
            k[x + 1][ y] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x + 1;
            M1[up][ 2] = y;
        }
        if ((x + 1 <= n)&&(y + 1 <= m)&&(k[x + 1][ y + 1] == inf)&&(a[x + 1][ y + 1]!=a[x][ y])&&(a[x + 1][ y + 1]!='0'))
        {
            k[x + 1][ y + 1] = k[x][ y] + 1;
            up++;
            M1[up][ 1] = x + 1;
            M1[up][ 2] = y + 1;
        }
        BFS(up, down);
    }
}

int min(int x, int y)
{
    if (x < y) return x;
    else return y;
}

void Solve(int up, int down)
{
    int x, y;
    down++;
    if (down <= up)
    {
        x = M1[down][ 1];
        y = M1[down][ 2];
        if ((x - 1 >= 1) && (y - 1 >= 1) && ((k[x - 1][y - 1] == k[x][y]) || (k[x - 1][y - 1] == k[x][y] + 1)))
        {
            if (d[x - 1][y - 1] == inf)
            {
                up++;
                M1[up][ 1] = x - 1;
                M1[up][ 2] = y - 1;
            }
            d[x - 1][ y - 1]= min(d[x - 1][ y - 1], d[x][ y] + 1);
        }
        if ((x - 1 >= 1) && ((k[x - 1][y] == k[x][y]) || (k[x - 1][y] == k[x][y] + 1)))
        {
            if (d[x - 1][y] == inf)
            {
                up++;
                M1[up][ 1] = x - 1;
                M1[up][ 2] = y;
            }
            d[x - 1][ y] = min(d[x - 1][ y], d[x][ y] + 1);
        }
        if ((x - 1 >= 1) && (y + 1 <= m) && ((k[x - 1][y + 1] == k[x][y]) || (k[x - 1][y + 1] == k[x][y] + 1)))
        {
            if (d[x - 1][y + 1] == inf)
            {
                up++;
                M1[up][ 1] = x - 1;
                M1[up][ 2] = y + 1;
            }
            d[x - 1][ y + 1] = min(d[x - 1][ y + 1], d[x][ y] + 1);
        }
        if ((y - 1 >= 1)&&(k[x][ y - 1] == k[x][ y]) || (k[x][ y - 1] == k[x][ y] + 1))
        {
            if (d[x][y - 1] == inf)
            {
                up++;
                M1[up][1] = x;
                M1[up][2] = y - 1;
            }
            d[x][y - 1] = min(d[x][ y - 1], d[x][ y] + 1);
        }
        if ((y + 1 <= m) && ((k[x][y + 1] == k[x][y]) || (k[x][y + 1] == k[x][y] + 1)))
        {
            if (d[x][y + 1] == inf)
            {
                up++;
                M1[up][ 1] = x;
                M1[up][ 2] = y + 1;
            }
            d[x][ y + 1] = min(d[x][ y + 1], d[x][ y] + 1);
        }

        if ((x + 1 <= n) && (y - 1 >= 1) && ((k[x + 1][y - 1] == k[x][y]) || (k[x + 1][y - 1] == k[x][y] + 1)))
        {
            if (d[x + 1][ y - 1] == inf)
            {
                up++;
                M1[up][ 1] = x + 1;
                M1[up][ 2] = y - 1;
            }
            d[x + 1][ y - 1] = min(d[x + 1][ y - 1], d[x][ y] + 1);
        }
        if ((x + 1 <= n)&&((k[x + 1][ y] == k[x][ y]) || (k[x + 1][ y] == k[x][ y] + 1)))
        {
            if (d[x + 1][y] == inf)
            {
                up++;
                M1[up][ 1] = x + 1;
                M1[up][ 2] = y;
            }
            d[x + 1][ y] = min(d[x + 1][ y], d[x][ y] + 1);
        }
        if ((x + 1 <= n)&&(y + 1 <= m)&&((k[x + 1][ y + 1] == k[x][ y]) || (k[x + 1][ y + 1] == k[x][ y] + 1)))
        {
            if (d[x + 1][y + 1] == inf)
            {
                up++;
                M1[up][ 1] = x + 1;
                M1[up][ 2] = y + 1;
            }
            d[x + 1][ y + 1] = min(d[x + 1][ y + 1], d[x][ y] + 1);
        }
        Solve(up, down);
    }
}

void main()
{
    scanf("%d%d\n",&n, &m);
    scanf("%d%d\n",&xs, &ys);
    scanf("%d%d\n",&xf, &yf);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            scanf("%c",&a[i][j]);
            if (j == m) scanf("\n");
            k[i][j] = inf;
            d[i][j] = inf;
        }
    }


    k[xs][ ys] = 1;
    M1[1][ 1] = xs;
    M1[1][ 2] = ys;
    BFS(1, 0);

    d[xs][ ys] = 0;
    M1[1][ 1] = xs;
    M1[1][ 2] = ys;
    Solve(1, 0);

    if (k[xf][yf] == inf) printf("0 0");
    else printf("%d %d",d[xf][yf] + 1,k[xf][yf] - 1);
}

count of iterations <= 500*500*8*2+500*500*8<5 000 000