Mines problem is really interesting. What is more interesting is “How to test it!”
Let me explain the way i used to test my program. And i am surprised my local tester generated almost the same score as the judge for most of my submissions
Generate own mines field
Choose n randomly between 30 and 50
choose p randomly between 0 and 2 inclusive
declare an array map, which holds the complete data about mine field.
loop over whole array and for each cell choose a random number between 0 and 9 inclusive
If this number is less than p, place a mine, else dont!
Once placing mines is done. Calculate the number of mines. This is m. Then calculate k as per generation rules mentioned.
For all elements in map which dose not contain a mine, count the number of mines adjacent and store them in map itself. So map contains ‘M’ or a value between 0 and 8
So we are done with test data generation.
How to query?
when ever you want information about a cell. The tester returns map value. I.e, ‘M’ if a mine is there or the count. Note that tester is just a function with in the program!
say you want to neutralize map[i][j].
Then if map[i][j] do not contain mine, do nothing.
If it contains a mine. reduce mine count of all adjacent cells by 1. Then count number of mines adjacent to current cell and update map[i][j].
Check if my program is working correct!
We have counters for neutralize calls and query calls. We check that these are less than k and n*n respectively. Also check that map is not left with any mines at last.
This way when i run program locally , I loop over 100 times. Each time generate a map and solve it. Finally display the score. It worked perfect! score difference between online judge and my local score is less than 0.2.
Implementation - Here
Functions related to testing - generate(), localget(), localnut(), check(), main(), get(), nut()
Rest are logical functions.
P.S: Every time the data is generated randomly so how can you check which of two methods to solve is better? For this purpose i generated 100 testcases and stored to a file. I read from file and test for efficiency of score.
P.S: My program depends on 2 flags, SUBMIT, If its 0 it works in local mode. FROMFILE, 1 To get test data from file, else generate random data