5:41 AM
@Aconcagua Good morning, true
@Aconcagua I don't get it

6:13 AM
@Aconcagua though, I really liked the idea of just creating the right matrix, and then apply the previous code
so for this given input
```5 5

3 3

5 1```
n=5, m=5
our matrix would be filled with 0s for no valid moves or reaches, and 1s, for valid ones.
and the 1s will start from 3 3 till 5 1
right

6:49 AM
If you really want to materialise the matrix, then from 0,0 you can reach both 1, 2 and 2, 1 (corner has just two reachable fields, or only one, if one dimension has size 2).
From 0, 1, you can reach 1, 3 and 2, 0 and 2, 2.
0, 2 already has 4 edges:
1, 0
1, 4
2, 1
2, 3
And so on.
Exactly that same step you need for creating the matrix you can include in BFS as well:
If you ever reach 0,2, you'll visit the four nodes from above apart from the one you came from and those that got visited before...
Good morning, by the way...

7:04 AM
I see
So the code of storing the matrix would be something like this
```        int n, m, x1, y1, x2, y2;
int x_move[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int y_move[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
cin >> n >> m >> x1 >> y1 >> x2 >> y2;
vector<vector<int>> matrix(n, vector<int>(m));
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < m; j++) {
for (size_t k = 0; k < 8; k++) {
int next_i = i + x_move[k];
int next_j = j + y_move[k];
if (isInside(next_i, next_j, n, m, matrix))
matrix[next_i][next_j] = 1;
}

}

}```

That should do the trick...

and this is the updated isinside
```bool isInside(int x, int y, int N, int M, vector<vector<int>> &matrix) {
return x >= 0 && x < N && y >= 0 && y < M && matrix[x][y] == 0;
}```

Hm...
If reading the name word by word, then any field with an edge would get outside the board...

what do you mean
?

matrix[x][y] == 0
So if matrix[x][y] != 0, we would be outside the matrix?

7:10 AM
that's just a check if it was already filled

That check is actually more important!
Not at filling, though.
I'd assume that additional check inside might be even more expensive than the assignment itself...
Ah, wait...
You'd use the matrix only later on.

right

That check would be important if you'd use it instead of the matrix inside BFS directly

I see

Then I'd name the function 'isEdge' or similar...

7:13 AM
so it's redundant for now
?

Well, you set only the nodes you can reach from current node anyway.

right
so it wouldn't add any value when creating the matrix

So it would always result in true...

right
now
when would I use them

You could do it a bit more efficient, if you are interested...

7:16 AM
absolutley

Only fill half of the matrix with that algorithm and fill the other one symmetrically:
if you set x, y to 1, then do so for y, x as well.
Oh, and one important point:
What will be size of adjacency matrix for your 5x5 chess board?

for the given
source and target
or in terms of symmetry?

You create an adjacency matrix. What will be its size? That's independent from source and destination or symmetry...

n*m

So size of 5x5 for adjacency matrix???
Wrong...
25 x 25!
With a 5x5 board you have 5*5 = 25 fields, and between each there might be an edge.

7:22 AM
absolutley
right

So adjacency matrix, in general terms, would get a size of (n*m)^2

I meant just in terms of n and m
but the wholematrix
it will absolutley get (n*m)^2

The matrix quickly gets huge!
10x10 chess board would result in 100x100.

(2 ≤ n, m ≤ 20)

OK, so maximum:
20x20
Matrix then would have (20*20)^2 total size.

7:24 AM
yes

160 000 entries.

not so efficient?

Well, depends.

it d still be ok for our problem

20 x 20 has 400 fields.

7:26 AM
yes

Each of those 400 fields can have at most 8 edges.

right

So density of that matrix will be pretty low...
8/400 = 2%
Adjacency list would be better choice...

interesting
though, for our problem contraint

400 * 8 = 3200 entries (actually less).

7:29 AM
right

A 50th of...

right
that's a big difference

In maximum case only...

yes
but the above code for the matrix is correct
I would love to do all the optimizations
it's just I still have some other problems, and I would spare the time for them
since they're a bit challenging too

7:54 AM
this cpp.sh/4lrgu gives the result 3 5 as the shortest path, which is correct
Now I need to determine the steps count and the steps themselves
is it the same as the previous problem about components
sorry that one doesn't have the property for finding the shortest path