# 111-1 PDSA HW1
Due date: 9/16 21:00

# HW1: Board Game
The playing pieces in our board game are called stones. There are two types of stones: ‘O’ and ‘X’. A set of stones can be flipped if the connected stones are surrounded by another type of stones. **In this assignment, you are going to implement the function of “surrounded” when given a coordinate of the board.**

We define connected as: two stones of the same type next to each other vertically or horizontally are connected.

For example:

.XXOX
XOXO.
XXOX.
XXOXX
..XOX

The two red ‘O’ stones in the third column are connected.

**Also, we want to know how many regions are in the Board by calling function "countConnectedRegion".**

For the example above, there are 9 ConnectedRegions.
## Hint
* [2022/10/18 Solution Guide](https://hackmd.io/@IgOaf3OpTm-h06XhECSNOQ/r1kSYYomj)
## Template

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

class BoardGame {
    public BoardGame(int h, int w) // create a board of size h*w
    public void putStone(int[] x, int[] y, char stoneType) // put stones of the specified type on the board according to the coordinates
    public boolean surrounded(int x, int y) // Answer if the stone and its connected stones are surrounded by another type of stones
    public char getStoneType(int x, int y) // Get the type of the stone at (x,y)
    public int countConnectedRegions() // Get the number of connected regions in the board, including both types of the stones

    public static void main(String args[]){ 
        BoardGame g = new BoardGame(3,3); 
        g.putStone(new int[]{1}, new int[]{1}, 'O');
        System.out.println(g.surrounded(1, 1)); 
        System.out.println(g.countConnectedRegions()); 
        
        g.putStone(new int[]{0, 1, 1}, new int[]{1, 0, 2}, 'X');
        System.out.println(g.surrounded(1, 1)); 
        System.out.println(g.countConnectedRegions()); 

        g.putStone(new int[]{2},new int[]{1}, 'X');
        System.out.println(g.surrounded(1, 1));
        System.out.println(g.surrounded(2, 1)); 
        System.out.println(g.countConnectedRegions()); 

        g.putStone(new int[]{2}, new int[]{0}, 'O');
        System.out.println(g.surrounded(2, 0)); 
        System.out.println(g.countConnectedRegions()); 
    }
}

## Example
Given a board

...    ...    .X.    .X.    .X.
... -> .O. -> XOX -> XOX -> XOX
...    ...    ...    .X.    OX.


-> 

false
1
false
4
true
false
5
false
6

Note the stone at the corner or on the border will never be surrounded.
More example

#Both O are not surrounded by X
#there are 5 ConnectedRegions.

.X.
XOOX
.XX.

#Both O are surrounded by X
#there are 5 ConnectedRegions.

.XX
XOOX
.XX.

#Neither O or X is surrounded
#there are 6 ConnectedRegions.

OXO
XOX

#Neither O or X is surrounded
#there are 3 ConnectedRegions.

.XXXX
XO.OX
XXXXX

## Test Data
Time Limit 2s
* N is the number of stones on the board.
* M is the total times we call putStone or surrounded
* We guarantee there is stone at (x,y) when we call surrounded(x,y)
* And there is no stone at (x,y) when we call putStone(x,y).
This assignment does not include the implementation of the function flipStone.
We only call the public functinos: putStone, surrounded
Total 100 points (Not sure)
* 20 points: w,h < 3 M < 100 Simple
* 20 points: w,h <= 1001 M < 7000 Special Case
* 20 points: w,h <= 101 M < 1000
* 20 points: w,h <= 101 M < 4000
* 20 points: w,h <= 10001 M < 4000

# File Download
[Data for TestCase](https://drive.google.com/drive/folders/1HSoOPSzwW_0DYuNU7_2Tf0hEbVk2vo3l?usp=sharing)
[Lib](https://drive.google.com/drive/folders/1AM3qneAZWsL5kuuU8L6z7Yr4v0yGgYPL?usp=sharing)
[Test Code](https://drive.google.com/drive/folders/1oGg8w3TQCNgORVdbc3n3pSyNMU_obY7z?usp=sharing)

###### tags: `1111pdsa`