import java.util.Scanner;
import java.io.*;
import java.util.Arrays;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.awt.geom.*;
import java.util.Scanner;
import java.io.*;

public class KnightsTourABourai {

    int[][] chessBoard = new int[9][9];
    int[][] accessArray = new int [9][9];
    int e = 1;
    int f = 1;
    int myX = 1;
    int myY = 1;
    int row = 0;
    int col = 0;
    int knightMoveCount;
    ArrayList <Point2D.Double> possibleDirections = new ArrayList <Point2D.Double> ();
    ArrayList <Point2D.Double> workingDirections = new ArrayList <Point2D.Double> ();

    Random rand = new Random();

    public KnightsTourABourai() {
    }

    public void possibleMoves(){
        possibleDirections.add(new Point2D.Double(1,-2));
        possibleDirections.add(new Point2D.Double(2,-1));
        possibleDirections.add(new Point2D.Double(2,1));
        possibleDirections.add(new Point2D.Double(1,2));
        possibleDirections.add(new Point2D.Double(-1,2));
        possibleDirections.add(new Point2D.Double(-2,1));
        possibleDirections.add(new Point2D.Double(-2,-1));
        possibleDirections.add(new Point2D.Double(-1,-2));
    }

    public void scanAccess(){
        try{
            Scanner in = new Scanner (new File("access.txt"));
            e = 1;
            f = 1;
            while(in.hasNext()){
                for(e = 1; e < 9; e ++){
                    for(f = 1; f < 9;f++){
                        accessArray[e][f] = in.nextInt();
                    }
                }
            }
        }
        catch(IOException e){
            System.out.println(e.getMessage());
        }
        System.out.println(Arrays.deepToString(accessArray));
    }

    public void moveKnight(){
        for(int a = 0; a < possibleDirections.size(); a++){
            double y = possibleDirections.get(a).getY();
            double x = possibleDirections.get(a).getX();
            if(myY + y > 0 && myY + y < 9 && myX + x > 0 && myX + x < 9){
                if(chessBoard[myY + (int)y][myX + (int)x] == 0){
                    workingDirections.add(new Point2D.Double(myY + y,myX + x));
                }
            }
        }
    }

    public void addBoard(){
        moveKnight();
        while(workingDirections.size() > 0){
            int b = rand.nextInt(workingDirections.size());
            knightMoveCount++;
            myX = (int)workingDirections.get(b).getX();
            myY = (int)workingDirections.get(b).getY();
            for(int c = 0; c < workingDirections.size(); c++){
                if(accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()] > 0){
                    accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()]--;

                }
            }
            for(int c = 0; c < workingDirections.size(); c++){
                if(accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()] < 9 && accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()] > 0){
                    int d = accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()];
                    if(accessArray[(int)workingDirections.get(c).getX()][(int)workingDirections.get(c).getY()] <= d){
                        myY = (int)workingDirections.get(c).getX();
                        myX = (int)workingDirections.get(c).getY();
                    }

                }
            }
            chessBoard[myY][myX] = knightMoveCount;
            workingDirections.clear();
        }
//      System.out.println(Arrays.deepToString(accessArray));

    }

    public void printBoard(){
        System.out.println();
        System.out.print("    ");
        for(int i = 1; i <= 8; i++){
            System.out.print(i + "   ");
        }
        System.out.println();
        for(int rowNumber = 1; rowNumber < 9; rowNumber++){
            System.out.println();
            System.out.printf("%-4d", rowNumber);
                for(int colNumber = 1; colNumber < 9; colNumber++){
                    System.out.printf("%-3d ", chessBoard[rowNumber][colNumber]);
                }
        }
        System.out.println();
        System.out.println();
        System.out.println(knightMoveCount + " squares visted");
    }


}


class driver{
    public static void main(String[] args){
        KnightsTourABourai knight = new KnightsTourABourai();
        knight.possibleMoves();
        knight.scanAccess();
        for(int o = 0; o < 15; o++){
        for(int i = 0; i < 64; i++){
            knight.addBoard();
        }
        knight.printBoard();
        }


    }
}


public class LifeABourai {
    boolean[][] currentArray;
    boolean[][] nextArray;
    int count;
    int total;
    int totalRowTen;
    int totalColumnTen;
    int x;
    int y;
    Scanner in;

    public LifeABourai(){
    }

    public void readFile(){
        try{
            in = new Scanner(new File("life100.txt"));
            x = in.nextInt();
            y = in.nextInt();
            currentArray = new boolean[x][y];
            nextArray = new boolean[x][y];
            while(in.hasNext()){
                int rows = in.nextInt();
                int columns = in.nextInt();
                currentArray[rows - 1][columns - 1] = true;
            }
        }catch(IOException i){
            System.out.println("Error: " + i.getMessage());
        }
    }

    public void firstGeneration(){
        for(int row = 0; row < currentArray.length; row++){
            for(int col = 0; col < currentArray[0].length; col++){
                count = 0;
                if(row > 0 && row < currentArray.length - 1){
                    if(currentArray[row + 1][col] == true){
                        count++;
                    }
                    if(currentArray[row - 1][col] == true){
                        count++;
                    }
                    if(col > 0){
                        if(currentArray[row - 1][col - 1] == true){
                            count++;
                        }
                        if(currentArray[row][col - 1] == true){
                            count++;
                        }
                        if(currentArray[row + 1][col - 1] == true){
                            count++;
                        }
                    }
                    if(col < currentArray[0].length - 1){
                        if(currentArray[row][col + 1] == true){
                            count++;
                        }
                        if(currentArray[row - 1][col + 1] == true){
                            count++;
                        }
                        if(currentArray[row + 1][col + 1] == true){
                            count++;
                        }
                    }

                }
                else if(row == 0){
                    if(currentArray[row + 1][col] == true){
                        count++;
                    }
                    if(col > 0){
                        if(currentArray[row + 1][col - 1] == true){
                            count++;
                        }
                        if(currentArray[row][col - 1] == true){
                            count++;
                        }
                    }

                    if(col != currentArray[0].length- 1){
                        if(currentArray[row][col + 1] == true){
                            count++;
                        }
                        if(currentArray[row + 1][col + 1] == true){
                            count++;
                        }
                    }
                }
                else if(row == currentArray.length - 1){
                    if(currentArray[row - 1][col] == true){
                        count++;
                    }
                    if(col > 0){
                        if(currentArray[row][col - 1] == true){
                            count++;
                        }
                        if(currentArray[row - 1][col - 1] == true){
                            count++;
                        }
                    }
                    if(col != currentArray[0].length - 1){
                        if(currentArray[row][col + 1] == true){
                            count++;
                        }
                        if(currentArray[row - 1][col + 1] == true){
                            count++;
                        }
                    }
                }
                if(currentArray[row][col] == true){
                    if((count == 0 || count == 1 || count >= 4)){
                        nextArray[row][col] = false;
                    }
                    else if(count == 2 || count == 3){
                        nextArray[row][col] = true;
                    }
                }
                else if(currentArray[row][col] == false && count == 3){
                    nextArray[row][col] = true;
                }
            }
        }
        currentArray = nextArray;
        nextArray = new boolean[x][y];
    }

    public int countRowTen(){
        totalRowTen = 0;
        for(int newColumn = 0; newColumn < currentArray[10].length; newColumn++){
            if(currentArray[9][newColumn] == true){
                totalRowTen++;
            }
        }
        return totalRowTen;
    }

    public int countColumnTen(){
        totalColumnTen = 0;
        for(int newRow = 0; newRow < currentArray[10].length; newRow++){
            if(currentArray[newRow][9] == true){
                totalColumnTen++;
            }
        }
        return totalColumnTen;
    }

    public int countTotalLiving(){
        total = 0;
        for(int r = 0; r < currentArray.length; r++){
            for(int c = 0; c < currentArray[0].length; c++){
                if(currentArray[r][c] == true){
                    total++;
                }
            }
        }
        return total;
    }

    public void printGeneration(){
        System.out.println();
        System.out.print("    ");
        for(int i = 1; i <= currentArray.length; i++){
            System.out.print(i % 10);
        }
        System.out.println();
        for(int rowNumber = 0; rowNumber < currentArray.length; rowNumber++){
            System.out.println();
            System.out.printf("%-4d", rowNumber + 1);
                for(int colNumber = 0; colNumber < currentArray[0].length; colNumber++){
                    if(currentArray[rowNumber][colNumber] == true){
                        System.out.print('*');
                    }
                    else{
                        System.out.print(" ");
                    }
                }
        }
        System.out.println();
        System.out.println();
        System.out.print("Number in Row 10: " + countRowTen());
        System.out.println();
        System.out.print("Number in Column 10: " + countColumnTen());
        System.out.println();
        System.out.println("Number total: " + countTotalLiving());
    }
}
class driver{
    public static void main(String[] args){
        int a = 0;
        LifeABourai l= new LifeABourai();
        l.readFile();
        while(a < 5){
            l.firstGeneration();
            a++;
            l.printGeneration();
        }

    }
}