Problem Description

Now that Mr Panda has prioritised his assignments, he has created a lot of free time for himself by finishing his homework as quickly as possible. He has decided to spend his leisure time on his other obsession, GAMING. He recently got addicted to a game called Binding of Isaac (true story :P) and he needs your help with gameplay.

The Binding of Isaac is a two-dimensional action-adventure video game where the player controls Isaac or six of the unlockable characters as he traverses through the dungeons located underneath his mother's basement. Each floor of the dungeon consists of rooms that form a map as shown in the second image below, with each room being adjacent to at most four rooms as seen below. Each floor of the dungeon ends in a boss room, where the player must defeat the boss before being able to go down to the next floor.

There are many types of rooms in the Binding of Isaac, including monster rooms and item rooms. There is a type of special room known as the Super Secret Room which contains very good items for the player, however the room is normally unmarked on the map. The player must bomb the wall of an adjacent room to gain access and its location must be guessed. There is exactly one such room on each map and it cannot be outside of the map. The Super Secret Room can only border exactly one regular room.

Your job now is to help Mr Panda find the how many of the undiscovered rooms on the map cannot be the Super Secret Room so that he can conserve his bombs while searching for the rooms and use them while fighting monsters instead.

Some parts copied from http://bindingofisaac.wikia.com/

Implementation Details

Your program will have to implement the 3 functions below.

void startGame(int R, int C): The game starts on a map with R rows and C columns

void discover(int x, int y): The players discovers the regular room at coordinate (x,y) with room at top left hand corner having coordinates (0,0). Note that discovered rooms may not necessarily be next to each other due to the existence of teleportation items.

int findSSR(): This function should return the current number of undiscovered rooms on the map that cannot be the Super Secret Room

Refer to the template in under the "Attachments" tab for details. Edit the isaac.cpp file and run ./compile_cpp.sh to compile your code then use ./isaac to run.

Admendments/Important Clarification

The range of x in discover(x, y) is between 0 and R-1 inclusive while the range of y in discover (x, y) is between 0 and C-1 inclusive.

Limits

For the first 3 subtasks, findSSR() will only be called once

Subtask 1(5%): 0 < R,C ≤ 1000, at most 1000 rooms discovered

Subtask 2(10%): 0 < R,C ≤ 1000000, at most 1000 rooms discovered

Subtask 3(25%): 0 < R,C ≤ 1000000, at most 100000 rooms discovered

For the next 3 subtasks, findSSR() will be called no more times than discover(x,y)

Subtask 4(10%): 0 < R,C ≤ 1000, at most 1000 rooms discovered

Subtask 5(15%): 0 < R,C ≤ 1000000, at most 1000 rooms discovered

Subtask 6(35%): 0 < R,C ≤ 1000000, at most 100000 rooms discovered

Subtask 7(0%): Sample

Sample Input

10 10
D 0 0
D 1 1
D 2 1
D 3 1
F
D 0 1
D 0 2
D 2 3
F
D 4 1
D 2 2
D 5 1
F

Sample Output

2
3
3

Explanation: Refer to diagram above