/* Kasioopea 2014 * http://ksp.mff.cuni.cz/akce/kasiopea/ * * Autorské řešení úlohy 26-K-4: Městský ruch * * (Pro překlad nastavte svému překladači normu jazyka C na C99 * nebo novější. V gcc se o to postará přepínač -std=c99.) */ #include #define Max 1010 int R, S; int M[Max][Max]; // mapa města char C[Max]; int D[Max][Max][4]; int Dx[Max][Max][4]; // -1 se chápe jako nekonečno int min(int a, int b) { if (a == -1) return b; if (b == -1) return a; if (a > b) return b; return a; } // -1 se chápe jako nekonečno int min4(int a, int b, int c, int d) { return min(min(a, b), min(c, d)); } // Pro zadaný typ aktivity a směr pohybu určí všechna D[r][s] a Dx[r][s] // (Dx[r][s] jsou vzdálenosti, kdy je zakázáno využít vlastní políčko) // Směry: // 0 - nahoru a vlevo // 1 - dolů a vlevo // 2 - dolů a vpravo // 3 - nahoru a vpravo void vypln_tabulku(int typ, int smer) { for (int r = 0; r < R; r++) for (int s = 0; s < S; s++) D[r][s][smer] = Dx[r][s][smer] = 0; int r_od, r_do, s_od, s_do, dr, ds; if (smer == 0 || smer == 2) r_od = 0, r_do = R, dr = 1; if (smer == 1 || smer == 3) r_od = R-1, r_do = -1, dr = -1; if (smer == 0 || smer == 1) s_od = 0, s_do = S, ds = 1; if (smer == 2 || smer == 3) s_od = S-1, s_do = -1, ds = -1; for (int r = r_od; r != r_do; r += dr) { for (int s = s_od; s != s_do; s += ds) { Dx[r][s][smer] = -1; if (r - dr >= 0 && r - dr < R && D[r - dr][s][smer] != -1) Dx[r][s][smer] = D[r - dr][s][smer] + 1; if (s - ds >= 0 && s - ds < S && D[r][s - ds][smer] != -1) Dx[r][s][smer] = min(Dx[r][s][smer], D[r][s - ds][smer] + 1); if (M[r][s] == typ) D[r][s][smer] = 0; else D[r][s][smer] = Dx[r][s][smer]; } } } int main() { scanf("%d%d", &R, &S); for (int r = 0; r < R; r++) { scanf("%s", C); for (int s = 0; s < S; s++) M[r][s] = C[s] - '0'; } long long vysledek = 0; for (int typ = 0; typ < 10; typ++) { for (int smer = 0; smer < 4; smer++) vypln_tabulku(typ, smer); for (int r = 0; r < R; r++) for (int s = 0; s < S; s++) vysledek += min4(Dx[r][s][0], Dx[r][s][1], Dx[r][s][2], Dx[r][s][3]); } printf("%lld\n", 2*vysledek); return 0; }