gSnake.scala

package Main

import java.io.FileInputStream

import scala.annotation.tailrec
import scala.collection.immutable.HashMap
import scala.collection.mutable
import scala.io.StdIn


object Main extends App {

    case class Command(time:Int, direction:Char)
    case class Point(x:Int, y:Int)
    case class Snake(direction:Int, body:mutable.ListBuffer[Point]) // L T R B

//    Console.setIn(new FileInputStream("example.in"))

//    Console.setIn(new FileInputStream("D-small-practice.in"))
//    Console.setOut(new FileOutputStream("D-small-practice.out"))

    Console.setIn(new FileInputStream("D-large-practice.in"))
//    Console.setOut(new FileOutputStream("D-large-practice.out"))

    val LEFT = 0
    val TOP = 1
    val RIGHT = 2
    val BOTTOM = 3

    val movingX = Array(-1, 0, 1, 0)
    val movingY = Array(0, -1, 0, 1)

    def solve(r: Int, c: Int, commands: List[Command]):Int = {
        @tailrec
        def turn(snake:Snake, food:HashMap[Point, Int], commands: List[Command], turnId:Int=0): Int = {
            if (1000000000 == turnId || snake.body.tail.contains(snake.body.head)) {
                snake.body.length
            } else {
                if (commands.isEmpty) {
                    if (snake.direction == RIGHT || snake.direction == LEFT) {
                        if (!snake.body.tail.exists(_.y != snake.body.head.y)) {
                            val avail = (if (snake.body.head.y % 2 == 0) c / 2 else (c + 1) / 2) - food.count(_._1.y == snake.body.head.y)
                            return snake.body.length + avail
                        }
                    } else {
                        if (!snake.body.tail.exists(_.x != snake.body.head.x)) {
                            val avail = (if (snake.body.head.x % 2 == 0) r / 2 else (r + 1) / 2) - food.count(_._1.x == snake.body.head.x)
                            return snake.body.length + avail
                        }
                    }
                }
                val newHead = Point(
                    (snake.body.head.x + movingX(snake.direction) + c) % c,
                    (snake.body.head.y + movingY(snake.direction) + r) % r
                )
                val isFoodExist = (1 == (newHead.x + newHead.y) % 2) && !food.contains(newHead)
                val newFood = if (isFoodExist) food + (newHead -> 0) else food
                val newBody = newHead +: (if (isFoodExist) snake.body else snake.body.init)

                if (commands.nonEmpty && commands.head.time == turnId + 1) {
                    turn(Snake(if (commands.head.direction == 'R') (snake.direction + 1) % 4 else (snake.direction + 3) % 4, newBody), newFood, commands.tail, turnId + 1)
                } else {
                    turn(snake.copy(body = newBody), newFood, commands, turnId + 1)
                }
            }
        }

        val snake:Snake = Snake(RIGHT, mutable.ListBuffer(Point(0, 0)))
        turn(snake, HashMap(), commands)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { n =>
        val Array(s, r, c) = StdIn.readLine().split(" ").map(_.toInt)
        val commands = (1 to s).map((x) => {
            val Array(t, c) = StdIn.readLine().split(" ")
            Command(t.toInt, c(0))
        }).toList

        println(s"Case #$n: ${solve(r, c, commands)}")
    }
}