MineSweeper
Lab 5 (CS1101 AY2008/9 Semester 1)
This lab assignment is graded.
Date of release: 28 October 2008, Tuesday, 23:59.
Submission deadline: 5 November 2008, Wednesday, 23:59.
School of Computing, National University of Singapore

0 Introduction

(Return to Labs page.)

This is your fifth and last graded lab. We hope that you are ready for your PE :)

This lab requires you to do two exercises. Only the first exercise is graded. You are advised to review the material covered in chapters 1 through 11, and read Programming Style, Design and Marking Guidelines before attempting this lab assignment. You should not use syntax or constructs not covered in lectures; you shouldn't need to and may even be penalized for doing so (if the objective of the assignment is undermined). Unless a template is given, you should start each program afresh (ie. don't cut and paste and modify) so that you get sufficient practice with writing a complete Java program.

A word of advice: Code incrementally. Don't try to finish all parts of a program then compile it. Write your program in bits and pieces and compile frequently. Try to maintain a compilable program even while you are working on it. Submitting a compilable program that partially works is better than submitting an un-compilable one. This last point especially applies to the programming exams. Seriously, code incrementally.

Note that:

For more information on CourseMarker, please refer to CS1101X lab page.

For this lab, the number of submissions is set to 10. Only your last submission will be graded.

If you have any questions, you may post your queries in the IVLE forum of your respective lecture group. Do not post your programs (partial or complete) in the forum before the deadline!


1 Exercise 1: MineSweeper (100%)

1.1 Learning objectives

1.2 Task

The objective of Minesweeper is to locate all the mines as quickly as possible without uncovering any of them. If you uncover a mine, you lose the game.

MineSweeper Source: http://www.chezpoor.com/minesweeper/minecore.html

(Reference: Minesweeper help)

To get a better feel of the game, it is highly recommended you play it at least once! (You now have an excuse to play minesweeper in the school labs.) For convenience, you may play the JavaScript version of the game in the panel above.

The playing area is known as the grid. The grid contains w * h number of tiles, where w (width) is the number of tiles horizontally and h (height) is the number of tiles vertically. Each tile has a state, which is one of the following: {Uncovered, Covered, Marked, Questionable}. In addition, a tile may contain a single mine. The total number of mines may not exceed the size (the number of tiles) of the grid.

The states are explained below:

In this exercise, you will write a simple Minesweeper command line game program. You will notice that when you left click on a single empty tile with no neighboring mine, the area surrounding it is uncovered until a "border" with numbered tiles is reached. To keep things simple, you do not have to implement such automatic repeated uncovering of tiles. Hence, at every move you will only uncover at most a single tile. Furthermore, you will only display the grid and do not have to implement the other functionalities (such as the timer and number of remaining mines).

As such, you only have to consider the following cases.

Winning or Losing:

The game is won when ALL the non-mine tiles are uncovered. Therefore when winning, the remaining tiles are in one of the COVERED, MARKED, or QUESTIONABLE states, and they are are all mines. The game is lost immediately when a mine is uncovered.

Input

Since we require deterministic output in order to test your solution, we require you to read in the initial state of  the grid.

The first line of the input has two integers w and h separated by a space. The first integer w (width) is the number of tiles horizontally. The second integer h (height)is the number of tiles vertically. You may assume that 2 ≤ w ≤ 100 and 2 ≤ h ≤ 100 and w is not necessarily equal to h.

The next h lines contain w characters in each line. Each character is either a '=' or a '*', where '=' represents a safe tile and '*' represents a tile with the mine. The first line is the top-most row of the grid and the last line is the bottom-most row of the grid.

The next 1 or more lines consist of game play commands which consist of a single letter (indicating the command) which can be either 'L' (left click) or 'R' (right click) followed by a space, followed by an integer denoting the X-coordinate, followed by a space, followed by an integer denoting the Y-coordinate. You may assume that the X- and Y-coordinates are valid positions within the grid.

The last line is a single line containing the letter 'Q'.

We define the tile at the bottom-left corner as having the coordinates (1, 1). So a command "L 1 2" means a left-click command on the first-column (left-most column), second-row (the row immediately above the bottom-most row) tile.

Output

The output is a single line containing the text "LOST" if any of the commands uncovered a mine. The output is "WON" if all non-mine tiles have been uncovered. The output is "IN PROGRESS" if all the commands so far have not uncovered all non-mine tiles yet (that is, you have neither lost nor won the game yet.)

You may ignore all further input and end the game immediately (even before seeing the quit command 'Q') the moment you win or lose the game.

(While you are NOT required to print the grid itself, you should still do it so that you may test your MineSweeper game!)

1.3 Sample runs

Sample run using interactive input (user's input shown in blue; output shown in bold purple).
(The first 2 statements are commands you issue to compile and run your programs in command-line environment, so they are not part of the output.)

In this sample run #1 below, the user types in L 2 3 and the game is lost on the first input command and terminates immediately. Program ignores other commands.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
====
=*==
====
====
L 2 3
LOST
L 3 3
L 2 2
Q

In this sample run #2 below, the user types in R 2 3 before L 2 3 which marks the tile at (2, 3) as a mine. Since a tile is marked, left clicking on the tile does not do anything and the game proceeds to execute the other commands.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
====
=*==
====
====
R 2 3
L 2 3
L 3 3
L 2 2
Q
IN PROGRESS

In this sample run #3 below, the user types in R 2 3 TWICE before L 2 3 which marks the tile at (2, 3) as questionable. Since a tile is questionable, left clicking on the tile uncovers the tile and the game is lost.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
====
=*==
====
====
R 2 3
R 2 3
L 2 3
LOST
L 3 3
L 2 2
Q

In this sample run #4 below, the two non-mine tiles are uncovered and the game is won immediately. Marking (4,4) as questionable and (2, 2) as mine.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
****
=**=
****
****
R 4 4
R 4 4
R 2 2
L 1 3
L 4 3
WON
L 1 1
Q

In this sample run #5 below, only one of the two non-mine tiles are uncovered, therefore the game is still in progress.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
****
==**
****
****
L 1 3
Q
IN PROGRESS

In this sample run #6 shown below, the user quits before all non-mine tiles are uncovered. Therefore the game is still in progress.

$ javac MineSweeperGame.java
$ java MineSweeperGame
4 4
****
==**
****
****
R 1 1
L 1 3
Q
IN PROGRESS

As usual, you may try your own sample runs here:

1.4 Submission

Submit your program through CourseMarker.

1.5 Important notes


2 Exercise 2: Gecko (0%)

2.1 Learning objectives

2.2 Task

The following question is one of the six questions released in National Olympiad in Informatics (NOI) 2008. NOI is a four-hour programming contest in which each contestant is required to individually solve and program a solution to each of the given programming tasks. Contestants compete with one another from the various secondary schools and junior colleges who work on the same questions. You may view the algorithm to all questions (including this one!) here.

During the rainy season, one of the walls in the house is infested with mosquitoes. The wall is covered by h × w square tiles, where there are h rows of tiles from top to bottom, and w columns of tiles from left to right. Each tile has 1 to 1000 mosquitoes resting on it.


Figure 1.

A gecko wants to eat as many mosquitoes as possible, subject to the following restrictions. It starts by choosing any tile in the top row, and eats the mosquitoes in that tile. Then, it moves to a tile in the next lower row, eats the mosquitoes on the tile, and so on until it reaches the floor. When it moves from one tile to a tile in the next lower row, it can only move vertically down or diagonally to the left or right (see figure 1).

Given the values of h and w, and the number of mosquitoes resting on each tile, write a program to compute the maximum possible number of mosquitoes the gecko can eat in one single trip from the top to the bottom of the wall.

Example (Credits to A/P Martin Henz)

Figure 2.

In figure 2, we can see a representation of a wall of dimensions h = 6 and w = 5. The value on each cell represents the number of mosquitos.

Figure 3.

Figure 3 shows the best path for the Gecko in order to eat the most number of mosquitoes. Following this path, the Gecko will eat a total of 32 mosquitos.

Algorithm (Credits to A/P Martin Henz)

The algorithm is explained below.

Figure 4.

Let us consider just the first row in Figure 4. We can see that (2, 0) with 7 mosquitoes is the obvious choice for the gecko to be.

Now, let us consider the second row in Figure 4. The best way to reach any cell on the second row is to pick the best cell above it that can reach the cell! For example, to reach (0,1) with 2 mosquitoes, we would choose (0,0) instead of (1,1) to reach (0,1) because if the gecko chose that path, it would have eaten 5 mosquitoes instead of 3! So therefore the gecko would have eaten a maximum of 10 mosquitoes at the second row if it had travelled a path of (2, 0) then (2, 1).

Figure 5.


Hence, for each cell in row 2, we compute the best way to reach that cell (by simply looking at the cells above and adjacent to it). The result is shown in Figure 5. We continue doing this repeatedly until we reach the last row and we pick the cell with the most number of mosquitoes!

(Since the algorithm is already given, the program can be written quite easily. In fact, the solution consists of only about 40 lines! You are encouraged to do this even though this exercise is not graded.)

Input

The first line has two integers. The first integer w (1 ≤ w ≤ 500) is the number of columns of tiles on the wall. The second integer h (1 ≤ h≤ 500) is the number of rows of tiles on the wall.

Next there are h lines of inputs. The ith line specifies the number of mosquitoes in each tile of the top ith row. Each line has w integers, where each integer m (1 ≤ m ≤ 1000) is the number of mosquitoes on that tile. The integers are separated by a space character.

Output

The output is a single integer which is the maximum possible number of mosquitoes the gecko can eat in one single trip from the top to the bottom of the wall.

2.3 Sample run

Sample run using interactive input (user's input shown in blue; output shown in bold purple):

$ javac Gecko.java
$ java Gecko
5 6
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 7 2 5 1
32

You can try your own sample runs here:

2.4 Submission

Submit your program through CourseMarker. Note that this exercise will not be graded.

2.5 Important notes


3 Deadline

The deadline for handing in all programs is 5 November 2008, Wednesday, 23:59. Late submissions will NOT be accepted.




Fri Oct 24 14:41:17 SGT 2008