奇怪的打印机
奇怪的打印机
将所有的颜色节点看作图中的一个节点,判断是否存在拓扑序列
public boolean isPrintable(int[][] targetGrid){
//每一种颜色上下左右边界
int[][] margin=new int[4][61];
for(int i=0;i<margin.length;i++){
Arrays.fill(margin[i],-1);
}
boolean[][] isConnected=new boolean[61][61];//是否存在一种颜色的拓扑序列
int[] indeg=new int[61];//每一种颜色入度
for(int i=0;i<isConnected.length;i++){
Arrays.fill(isConnected[i],false);
}
Arrays.fill(indeg,0);
List<List<Integer>> g=new ArrayList<List<Integer>>();
for(int i=0;i<=60;i++){
g.add(new ArrayList<>());
}
int n=targetGrid.length;int m=targetGrid[0].length;
//对于每一个位置
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int curColor=targetGrid[i][j];
//当前颜色边界
margin[0][curColor]=margin[0][curColor]==-1? i:Math.min(i,margin[0][curColor]);
margin[1][curColor]=margin[1][curColor]==-1? i:Math.max(i,margin[1][curColor]);
margin[2][curColor]=margin[2][curColor]==-1? j:Math.min(j,margin[2][curColor]);
margin[3][curColor]=margin[3][curColor]==-1? j:Math.max(j,margin[3][curColor]);
}
}
//创建图,
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int curColor=targetGrid[i][j];
//对于每一种颜色
for(int color=1;color<=60;color++){//每一种可以包含curColor的颜色都可以在之前染色
if(color!=curColor&&!isConnected[color][curColor]&&margin[0][color]<=i&&i<=margin[1][color]
&&margin[2][color]<=j&&j<=margin[3][color]){
isConnected[color][curColor]=true;
g.get(color).add(curColor);
indeg[curColor]++;
}
}
}
}
//拓扑排序
Queue<Integer> queue=new LinkedList<Integer>();
for(int i=1;i<=60;i++){
if(indeg[i]==0){
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int node=queue.poll();
//所有连接边
for (Integer v : g.get(node)) {
indeg[v]--;
if(indeg[v]==0){
queue.offer(v);
}
}
}
int ans=0;
for(int i=1;i<=60;i++){
ans+=indeg[i]==0? 1:0;
}
return ans==60;
}