Problem I. 378. (May 2015)
I. 378. We are given a black-and-white image of \(\displaystyle N\times M\) pixels, described by 0s and 1s arranged in a grid. An image is considered to be nicer, if there are more adjacent pixels that are identical. In this exercise, two pixels are adjacent if they share a common edge. Your goal is to make the original image nicer by negating certain pixel values. Negating the value of a single pixel costs \(\displaystyle Q\) units of money. However, in the final image, every pair of adjacent pixels with different colors will result in an additional penalty of \(\displaystyle P\) units of money.
For some given images you should find the transformation such that the sum of the \(\displaystyle P\) and \(\displaystyle Q\) quantities is the smallest.
Without submitting a program, your task now is the convert the three input files in.1, in.2 and in.3 (downloadable from our web site) to out.1, out.2 and out.3. The first line of an input file contains 4 integers (\(\displaystyle N\), \(\displaystyle M\), \(\displaystyle P\) and \(\displaystyle Q\)), describing the number of rows and columns of the grid, and the cost and penalty parameters. The image itself is described in the following \(\displaystyle N\) lines, each containing \(\displaystyle M\) characters. The output should have a similar format with an \(\displaystyle N\times M\) grid of pixel values. You are not required to submit an optimal solution, but solutions will compete against one another: the solution with the smallest total \(\displaystyle P+Q\) value for the 3 images will obtain 10 points, and other, suboptimal solutions will get proportionally less points.
A sample input file is presented below, together with a possible (not necessarily optimal) transformation. The total cost \(\displaystyle P+Q\) here is \(\displaystyle 6\cdot 2+3\cdot 3 =21\) units of money.
The three output files should be submitted in a compressed file (i378.zip).
Deadline expired on June 10, 2015.
6 students sent a solution. 10 points: Gercsó Márk. 9 points: Kovács 246 Benedek. 8 points: 1 student. 7 points: 1 student. 6 points: 1 student. 5 points: 1 student.