@Aconcagua Good morning, true

@Aconcagua I don't get it

@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

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:

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...

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?

that's just a check if it was already filled

we don't care about it

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...

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

about x1, x2, y1, y2

when would I use them

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

absolutley

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.

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.

yes

160 000 entries.

not so efficient?

Well, depends.

it d still be ok for our problem

20 x 20 has 400 fields.

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).

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

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

so when I will apply the source and destination vertices to the BFS function

I have x1, y1, x2, y2

I would select x1, as source, and x2 as destination, right?

Also, the above matrix creation code is correct?

the path 3 5 with size 1 is not correct

I found many examples online, of how to not create the matrix, but incorporate the checks inside the bfs

but it would be really interesting to know how it ll work setting the right matrix for the bfs

please the above code has some horrible mistakes

Well, remember how we got from a 20x20 matrix to a 400x400 matrix??? Your code doesn't contain anything of that.

Remember we have to matrices, once the chess board, once the adjacency matrix. They are not the same. Adjacency matrix is a square one. Always....