|
|
back to boardDiscussion of Problem 1325. DirtWhy o(nm) get TL? #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 |
|
|