DAY 5
0
Software Development

# 6 拓樸排序問題

## 6.1 Leetcode 329. Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

``````class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> maxlen(m, vector<int>(n, 0));
std::function<void(int, int)> dfs = [&](int x, int y) {
maxlen[x][y] = 1;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
for (int f = 0; f < 4; f++) {
if (x + dx[f] >= 0 && x + dx[f] < m && y + dy[f] >= 0 &&
y + dy[f] < n) {
if (matrix[x + dx[f]][y + dy[f]] > matrix[x][y]) {
if (maxlen[x + dx[f]][y + dy[f]] == 0) {
dfs(x + dx[f], y + dy[f]);
}
maxlen[x][y] = max(maxlen[x][y], maxlen[x + dx[f]][y + dy[f]] + 1);
}
}
}
};
int answer = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (maxlen[i][j] == 0) dfs(i, j);
}
}
};
``````

## 6.2 Leetcode 1591. Strange Printer II

https://leetcode.com/problems/strange-printer-ii/

``````class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
// 首先找出每個矩形邊界
int m = targetGrid.size();
int n = targetGrid[0].size();
map<int, vector<int>> colorsBoundary;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (colorsBoundary.find(targetGrid[i][j]) == colorsBoundary.end()) {
colorsBoundary[targetGrid[i][j]] = {i, i, j, j};
} else {
vector<int>& bounds = colorsBoundary[targetGrid[i][j]];
bounds[0] = min(bounds[0], i);
bounds[1] = max(bounds[1], i);
bounds[2] = min(bounds[2], j);
bounds[3] = max(bounds[3], j);
}
// 接下來找出相依關係
map<int, set<int>> dependencyGraph;
for (auto it : colorsBoundary) {
int color = it.first;
vector<int> bounds = it.second;
for (int i = bounds[0]; i <= bounds[1]; i++)
for (int j = bounds[2]; j <= bounds[3]; j++)
if (targetGrid[i][j] != color)
dependencyGraph[targetGrid[i][j]].insert(color);
}
// 然後跑一次拓樸排序(或是發現圖上有環，失敗)
map<int, int> visited;
vector<int> toposort;
bool has_cycle = false;
std::function<void(int)> dfs = [&](int x) {
visited[x] = 1;
for (int y : dependencyGraph[x]) {
if (visited.find(y) != visited.end()) {
if (visited[y] == 1) has_cycle = true;
} else {
dfs(y);
}
}
visited[x] = 2;
toposort.push_back(x);
};
for (auto it : colorsBoundary) {
int color = it.first;
if (visited.find(color) == visited.end()) dfs(color);
}
if (has_cycle) return false;
// 最後模擬一次畫矩形的順序
vector<vector<int>> grid(m, vector<int>(n, 0));
for (int color : toposort) {
vector<int> bounds = colorsBoundary[color];
for (int i = bounds[0]; i <= bounds[1]; i++)
for (int j = bounds[2]; j <= bounds[3]; j++) grid[i][j] = color;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] != targetGrid[i][j]) return false;
return true;
}
};
``````