# Trend Micro Written Test Review (Algorithm Question 2)

2022-08-06 18:08:44

Title description:

• There is a two-dimensional matrix, the elements are composed of 0 or 1, and the adjacent (only up, down, left, and right) 1s form a graph.
• Manhattan distance is defined as the value of abs(x1-x2)+abs(y1-y2) between two points.
• Find the number of graphs for a given matrix and the maximum Manhattan distance between two points in the graph.

Thinking:

This is a typical island problem, but the index of solving the distance within the island is added to the island problem;

My idea is to use a two-dimensional array to record each point of a graph, and then calculate it in pairs to find the maximum distance;

(The original idea was to record a top left point and a bottom right point. Later, when I realized it, I found that the left and top conflicted, and the time was urgent, so I directly chose to solve it by violence. Now think back to the left and the top.The top is in conflict, so can we record the top left and top left points, as well as the bottom right and bottom right points to find the maximum value among the four combinations? To be verified!)

Solution:

Only passed 96.67% of the test cases during the exam. Now I have found the problem and posted the changed code:

``vector> path;void dfs(vector>& graph, int i, int j, vector>& used) {if (i < 0 || i >= graph.size() || j < 0 || j >= graph[0].size() || used[i][j] == true) return;if (graph[i][j] == 0) return;used[i][j] = true;path.push_back({i, j});dfs(graph, i + 1, j, used);dfs(graph, i - 1, j, used);dfs(graph, i, j + 1, used);dfs(graph, i, j - 1, used);}vector solve(vector>& graph) {vector res = {0, 0};int m = graph.size(), n = graph[0].size();vector> used(m, vector(n, false));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (graph[i][j] == 1 && used[i][j] == false) {res[0]++;path.clear();dfs(graph, i, j, used);for (int x = 0; x < path. size(); ++x) {for (int y = x + 1; y < path. size(); ++y) {int tmp = abs(path[x][0] - path[y][0]) + abs(path[x][1] - path[y][1]);res[1] = max(res[1], tmp);}}}}}return res;}``

Maybe I was too nervous during the exam. When trying to find the maximum distance violently after calling dfs, I still used two loop variables i and j (so that I can pass 96.67?), be sure to pay attention to this problem next time!!!

In addition, the first question of the algorithm question is a simple string replacement operation, so I won't repeat it.