Robotić WALL-E se još od Okružnog takmičenja usamljen igra na deponiji smeća i to mu već pomalo postaje dosadno. Kako bi stao na put dokolici, priredio je veliku žurku na deponiji na koju je pozvao sve svoje metalne drugare sa fejsbuka. Robotska žurka se odvija standardno: Svaki robotić zauzme jedno polje matrice koja predstavlja deponiju i zamisli jedan od četiri moguća pravca u kom želi da načini korak. Potom se robotići istovremeno pomere, svaki za tačno jedan korak u svom željenom pravcu. Tako se nađu na novim pozicijama i žurka se završava (sve što je dobro traje kratko).

Međutim, odaziv je bio veoma velik i na žurci se napravila prilična gužva. Zbog toga nisu svi robotići u stanju da načine željeni korak. Da bi robotić uspeo da ode na polje na koje je zamislio, ni jedan drugi robotić se ne sme naći na tom polju nakon odigranog koraka. To znači da od svih robotića koji žele da dođu na neko polje samo jedan može da uspe u tome, i to samo ako robotić koji je prethodno bio na tom polju uspe da ga napusti. U toku koraka robotići se mogu mimoilaziti bez problema, ali po izvršenju koraka na svakom polju se sme nalaziti najviše jedan robotić.

WALL-E želi da mu žurka koliko-toliko uspe i da usreći što više svojih drugara. On treba da odabere najveći mogući broj robotića koji će moći da naprave korak, dok će svi ostali morati da ostanu na svojim pozicijama. Koliko najviše robotića može napraviti korak?

Ulaz.

(Ulazni podaci se učitavaju iz datoteke robotici.in.) U prvom redu nalaze se dva broja m i n (1 ≤ m, n ≤ 200), dimenzije matrice koja predstavlja deponiju. U svakom od sledećih m redova nalazi se n razmakom razdvojenih brojeva koji predstavljaju polja. Brojevi označavaju šta se nalazi na odgovarajućem polju i imaju sledeća značenja:

1. 0 - prazno polje
2. 1 - robotić koji želi da napravi korak na desno
3. 2 - robotić koji želi da napravi korak na gore
4. 3 - robotić koji želi da napravi korak na levo
5. 4 - robotić koji želi da napravi korak na dole

Nijedan robotić neće poželeti da napusti deponiju za vreme žurke (tj. napravi korak van matrice).

Izlaz.

(Izlazne podatke upisati u datoteku robotici.out) Na izlaz ispisati samo jedan broj - koliko najviše robotića moće da načini korak.

Primer 1.

4 5
0 0 0 0 0
0 1 1 4 0
0 2 0 1 0
0 0 0 0 0

5

Primer 2.

4 3
0 0 0
0 4 0
0 2 0
0 0 0

2

#include <iostream>
#include <cstdio>
using namespace std;

const int MaxN = 201;

int move[][2] = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} };

int n, m;
int smer[MaxN][MaxN];
int inv[MaxN][MaxN];

long lvl[MaxN][MaxN];

long marker[MaxN][MaxN];
long markID;


long najdublje(int i, int j)
{
  // markiraj
  lvl[i][j] = -1;

  long najduboko = 0;
  for (int k = 0; k < 4; k++)
  {
    if (inv[i][j] & (1<<k))
      najduboko = max(najduboko, 1 + najdublje(i + move[k][0], j + move[k][1]));
  }
  return najduboko;
}

long ciklus(int i, int j, int dubina)
{
  // markiraj
  lvl[i][j] = dubina;
  marker[i][j] = markID;

  int in = i + move[smer[i][j] - 1][0], jn = j + move[smer[i][j] - 1][1];
  if (lvl[in][jn] == 0)
    return ciklus(in, jn, dubina + 1);
  else if (marker[in][jn] != markID)
    return 0;
  else
    return dubina - lvl[in][jn] + 1;
}

int main()
{
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      scanf("%d", &smer[i][j]);

  // obrnuto
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      inv[i][j] = 0;
      if (j < m - 1 && smer[i][j+1] == 3)
        inv[i][j] |= 1;

      if (i > 0 && smer[i-1][j] == 4)
        inv[i][j] |= 2;

      if (j > 0 && smer[i][j-1] == 1)
        inv[i][j] |= 4;

      if (i < n - 1 && smer[i+1][j] == 2)
        inv[i][j] |= 8;
    }


  memset(lvl, 0, sizeof(lvl));
  long longestPath = 0;

  // drvece
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      // koren drveta
      if (smer[i][j] == 0)
      {
        long deep = najdublje(i, j);
        longestPath += deep;
      }
    }

  // ciklusi
  memset(marker, 0, sizeof(marker));
  markID = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      // nije markiran, trazimo ciklus
      if (lvl[i][j] == 0 && smer[i][j] != 0)
      {
        long cycle = ciklus(i, j, 0);
        longestPath += cycle;
        markID++;
      }
    }

  printf("%ld\n", longestPath);
  return 0;
}

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;


class Cell {
  int y, x;

  public Cell(int y, int x) {
    this.y = y;
    this.x = x;
  }
}


public class Robotici {
  static final int[] dy = new int[] {0, 0, -1, 0, 1};
  static final int[] dx = new int[] {0, 1, 0, -1, 0};
  String fileIn, fileOut;
  
  int ny, nx;
  int[][] dir;
  int[][] color;
  int[][] rank;
  int maxDancers;


  Cell paint(int startY, int startX, int colorOld, int colorNew) {
    int l = 0;
    int y = startY;
    int x = startX;
    
    while (dir[y][x] != 0 && color[y][x] == colorOld) {
      color[y][x] = colorNew;
      l++;
      int d = dir[y][x];
      y += dy[d];
      x += dx[d];
    }
    
    int r = l + rank[y][x];
    y = startY;
    x = startX;
    
    for (int i = 0; i < l; i++) {
      rank[y][x] = r--;
      int d = dir[y][x];
      y += dy[d];
      x += dx[d];
    }
      
    return new Cell(y, x);
  }

  
  void solve() {
    color = new int[ny][nx];
    rank = new int[ny][nx];
    
    int currentColor = 1;
    for (int y = 0; y < ny; y++)
      for (int x = 0; x < nx; x++)
        if (dir[y][x] != 0 && color[y][x] == 0) {
          Cell front = paint(y, x, 0, currentColor);
          int c = color[front.y][front.x];
          
          if (c == 0)                                        // 1) naisli smo na slobodno polje 
            color[front.y][front.x] = currentColor;
          else                                              
            if (c == currentColor)  {                      // 2) napravili smo petlju, rep blokira
              paint(front.y, front.x, currentColor, -1);
              paint(y, x, currentColor, -2);
            } else {
              if (c < 0)                                 // 3) udarili smo u petlju ili blokirani lanac, blokiramo
                paint(y, x, currentColor, -2);
              else                                       // 4) pridruzujemo se postojecem lancu koji ne blokira
                paint(y, x, currentColor, c);
            }
          
          currentColor++;
        }

    maxDancers = 0;
    
    int[] maxColorRank = new int[currentColor];
    for (int y = 0; y < ny; y++)
      for (int x = 0; x < nx; x++) {
        int c = color[y][x];
        if (c == -1)
          maxDancers++;                                      // u petlji se svi krecu
        if (c > 0)
          if (rank[y][x] > maxColorRank[c])                  // u ostalim grupama samo najduzi lanac 
            maxColorRank[c] = rank[y][x];
      }
    
    for (int maxRank : maxColorRank)
      maxDancers += maxRank;
  }

  
  void readInput() throws FileNotFoundException {
    Scanner in = new Scanner(new File(fileIn));
    
    ny = in.nextInt();
    nx = in.nextInt();
    dir = new int[ny][nx];
    for (int y = 0; y < ny; y++)
      for (int x = 0; x < nx; x++)
        dir[y][x] = in.nextInt();
    
    in.close();
  }
  

  void writeOutput() throws IOException {
    PrintWriter out = new PrintWriter(fileOut);
    out.print(maxDancers);
    out.close();
  }
  
  
  public Robotici(String fileIn, String fileOut) {
    this.fileIn = fileIn;
    this.fileOut = fileOut;
    
    try {
      readInput();
      solve();
      writeOutput();
    } catch (Exception e) {
      e.printStackTrace();
    }
  }
  

  public static void main(String[] args) {
    new Robotici("robotici.in", "robotici.out");
  }
}