« first day (13 days earlier)   

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
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...
 
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
about x1, x2, y1, y2
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
 

« first day (13 days earlier)