CODEWITHSUNDEEP
c++algorithmgraph
AgentWiggles
AgentWiggles

Reputation: 45

Finding connected components in an implicit representation of a graph

I have a CS problem for school that I just can't seem to wrap my head around.

We're given a vector of strings, which composes an "image". This vector of strings effectively represents a 2 dimensional matrix, and, in each of the spaces, there can be one of 4 characters: 'K' - A knight, 'D' - a dragon, '#' - a castle wall, and ' ' - empty space.

The problem requires us to write several functions, for instance: safe_knights - which finds how many knights are positioned such that dragons cannot move to them, castle_count - which counts the castles in the image, and knights_in_castles - which counts how many knights reside within castles. (see definitions below)

The assignment is somewhat vague, and I'm confused as to where to begin with this. The one hint that I have is that we should be looking for connected components of spaces - if I knew which spaces are connected, I'd be able to determine whether a dragon has a path to a knight (safe_knights needs this), or if a region of spaces is enclosed by castle walls (would be used for castle_count).

I know that I can use one of the graph traversal algorithms to help find connected components, but I'm scratching my head over how to implement this to work on the graph which is represented implicitly in the vector of strings. The pieces just aren't coming together for me.

Any hints or ideas to point me in the right direction would be appreciated!

//Definitions of terms above:

A castle is a region of at least one space enclosed by walls. Walls are connected if they are orthogonal or on the same line, not diagonal.

Castles:                      ||   Not Castles:
####     ###    ######        ||   ##       ###     # 
#  #     # #    #    ####     ||   # #      # #     #
####     # #    #       #     ||   ###       #      ####  
         ###    #########     ||

A knight is safe if there is no dragon that can move to it. Dragons cannot move diagonally.

Safe Knights:     ||     Tasty Knights:
###     ###       ||     #####         ###  D
#K# D   # K#      ||     #K  D#        # #  K
###     ###  D    ||     #####         ####

Example question to clarify what I don't understand:

The vector of strings is called image.

Say that (i, j) is equivalent to the character at (image[i])[j] (i.e. the jth char in the string at image[i].)

Then, how can I look at (i,j) and say "this is in a castle" or "this space can be reached by the dragon at (m,n)"?

Do I need some kind of tracking, like storing known connected components as a member of the class?

I'm assuming that each point (i,j) is a vertex in the graph, so I think I need some way to look at (i,j) and decide which other vertices it's adjacent to. I was told by the instructor that I don't need to represent the graph separately (e.g. scan through the vector and construct an adjacency matrix.) So I need to operate on the graph implicitly as opposed to having an explicit representation.

Edit: So, I've thought about this some more, and it seems like the basis of each function is going to be doing a traversal, with slightly different stipulations on what constitutes adjacency. For example:

safe_knights - starting with a knight, DFS to legal spaces until a dragon is found or no more moves can be made. legal spaces are those in cardinal directions not blocked by a wall or the edge of the board.

castle_count - starting with a wall, DFS to spaces in cardinal directions containing walls, until this can't be done anymore. I think I'm going to also need some way to tell whether I've made it all the way back to where I started - maybe I can remember that starting node within that function. I might also have to check if there's a space in the middle.

knights_in_castles - this one is a little confusing - maybe starting with each knight, check the spaces around him until a wall is found, then check if that wall is part of a castle?

Upvotes: 0

Views: 448

Answers (1)

Tao HE
Tao HE

Reputation: 300

I guess your problem is how to use an incidence matrix (storing edge length in each cell) to represent the chessboard, before you apply ordinary graph traversal algorithm on it. Yet actually there is no need to do this.

Normally on a chessboard, we directly use the board matrix to represent this problem, no need to store edge length in a cell. If we want to find connected components, we use depth-first search (DFS) or breadth-first search (BFS) or A* search to find them.

A recursive DFS algorithm is quite simple to implement, but a little hard to understand at first.

DFS(node v)
{
    visit(v);
    for each child w of v {
    // On a chessboard, they are right, left, up, and down neighbor cells
        DFS(w);
    }
}
  1. In most cases, we use a global flag matrix to mark which cell has been visited.
  2. Before 'visit(v)', we always need to check that v is a legal cell (by check coordinates not over bound).

For example, if want the 'safe_knights', we start with a knight, DFS recursively search neighbor legal (not over bound, not a wall) cells, until we encounter a dragon, and fast return.

Upvotes: 1

Related Questions