If we were doing the 11 by 11 case and we were trying to build a
graph, we can see that we'd have a 121 nodes
there, then we'd use this natural mapping, the natural two dimensional mapping.
And then we'd make a list of nodes, and each node would be
connecting a pair of i, j coordinates and we are going
to privately store this in this data structure.
A vector, a deque of ints.
This is not, this is not unique.
Actually, this could just as well have been a vector.
And here's the critical thing for creating an edge for an internal node.
Recall that, when we have corner nodes like (0,0),
so if this is the zero zeroth node, it only has two nodes that it connects to.
But if I have an internal node, an
i, j, where they're not equal to
zero, they're also
not equal to 10. So they're not on the perimeter.
So, there because it's a hexagon, you have the six possible
connections, the two above, the two on the same row, and the two below.
And that's what all of these indices, show you.
This is how to connect.
And this is a mapping of the i, j coordinates into the node numbers.
So this
is saying, push onto the node a particular, edge connection,
so I just give you a piece of code like that so you can make use of it.
When you go to do your own version of
this, you're going to need to do the special cases.
So the general case is, six things in the middle.
Special cases will not involve all the six things.
Recall that if you have corners, it is only two nodes, if you have,
if there are only. Two nodes adjacent to a corner node, and
if you have an edge node that's not a corner, then you have four adjacent nodes.
The edge nodes have, if let's say, you're on a, a, a side,
you have the above one, the below one, and then two internal ones.
Okay so you'll still need to test among the things you'll need
to be able to do is you'll be able to from the
code we just looked at get a full graph representation.
You'll need to be able to test when the game is over, and who won.
Here's where you could use your own form of Dijkstra.
Who won is somebody who one that created a path from, for example,
east, so there's some path from east to west.
East is all the nodes on this boundary, so it's collection of,
in the case of, the 11 by 11, there
are 12, there are 11 east nodes here, and 11 west nodes.
And you want to see if there's a path from any of these east nodes.
That need these west nodes, and if you find a path, doesn't even have to be a
shortest path, well, it'll be the only path
because when it happens, the game will be over.
So it'll be the shortest path from some node on the east to
some node on the west and that's where you can use your Dijkstra.
And then.
The other thing I want is something like
a simple strategy, like extending a longest path.
There we go. We're blocking.
So that's your job.
So, among the things you should be able already to think about is,
how would you test, what would be a test for a corner node?
Take a sec.
Here's an answer for upper left corner.
It's just some series of boolean expressions.
Now, we've left two off,
Let's see if, on the fly, I can remember one, so
there'd be another one like, this again is the logical and.
So this would be yet another corner.
And the final corner would be, so
that gives you all four corners. Okay?