oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

jawbreak Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

jawbreak.html

Jawbreaker is a simple game that is often bundled with PDAs and handphones. A player starts with a board filled with coloured balls. The player can select any group of 3 or more adjacent, like-coloured balls to make them disappear. When the selected balls are removed, balls in the same column(s) above the removed balls fall down, leaving empty space at the top. If any columns become empty as a result of this, the remaining columns to the right of the empty columns are compacted to the left, leaving empty space on the right of the board.

A player start with a score of 0. Each move adds to the player's score by the square of the number of balls removed. A player wins Jawbreaker if he/she is able to remove all balls from the board. A win adds a bonus of 1,000 points to the score. The game is over if there are no valid moves remaining on the board.

Adjacent means balls directly above, below or to the left or right. Diagonally touching balls are considered not adjacent.

In this problem, you are given a n x n Jawbreaker board with m colours. Your program should output the maximum score that can be achieved given the board.

Input

The first input line gives the size of the board n and the number of colours m, where (1 ≤ n ≤ 8 and 1 ≤ m ≤ 4). The remaining n lines give the initial board, where each of n characters in the line is a number 1 to m, indicating its colour.

Output

Output the maximum score that can be achieved from the initial board.

Sample Input 1

3 3
113
211
112

Sample Output 1

36

Explanation for Sample Output 1

For Example 1, there is only one valid move to remove the group of six 1s, which results in the following board ('-' indicate empty spaces). Note that after the removal of the group of 1s, the second column is empty and is compacted.

---
-3-
22-

No subsequent moves are possible.

Sample Input 2

4 3
3222
3211
2212
3322

Sample Output 2

1106

Explanation for Sample Output 2

For Example 2, there are three possible initial moves. Only the removal of the group of three 1s allows the two groups of 2s to collapse into one large group that will result in the maximum score.

Tags

NOI 2007, Ad Hoc

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110051s32MBAverage
2021s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o jawbreak -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.