题目:1088
题意:求矩阵中的最长递减长度
题解:拓扑排序(剥洋葱)
AC代码:
#include<iostream>
#include<vector>
using namespace std;
#define MAX 100
int cnt;
int dir[4][2] = { {0,1}, {0,-1}, {1, 0}, {-1, 0} };
int matrix[MAX][MAX];
int outdegree[MAX][MAX] = {0};
vector<int> v;
int main() {
int r, c;
int tx, ty; //坐标的临时变量
cnt = 0;
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> matrix[i][j];
for (int i = 0; i < r; i++) //计算所有点的出度
for (int j = 0; j < c; j++)
for (int k = 0; k < 4; k++) {
tx = i + dir[k][0];
ty = j + dir[k][1];
if (tx < r && tx >= 0 && ty < c && ty >= 0 && matrix[i][j] < matrix[tx][ty])
outdegree[i][j]++;
}
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (!outdegree[i][j])
v.push_back(i*c + j);
while (!v.empty()) { //剥洋葱算法
cnt++;
vector<int> newv;
for (int i = 0; i < v.size(); i++) {
int x = v[i] / c;
int y = v[i] % c;
for (int j = 0; j < 4; j++) {
tx = x + dir[j][0];
ty = y + dir[j][1];
if (tx < r && tx >= 0 && ty < c && ty >= 0 && matrix[x][y] > matrix[tx][ty])
if (--outdegree[tx][ty] == 0)newv.push_back(tx*c + ty);
}
}
v = newv;
}
cout << cnt << endl;
return 0;
}
Net_Black_Fox 发布了27 篇原创文章 · 获赞 3 · 访问量 1738 私信 关注