算法笔记之 拓扑排序 POJ 2585(Window Pains)
http://poj.org/problem?id=2585
此题中，每个窗口的位置是固定的。主要就是通过覆盖关系，来建立拓扑排序。如果可以排序，就说明没有问题。
重点在这里。
//比如在地图中的[2][2]位置，可以放置{1,2,4,5},如果这个地方显示的是5，则说明 5覆盖了1,2,4
static int dir[][][]= { //每个位置可以放置哪些窗口
{ {1},{1,2},{2,3},{3} },
{ {1,4},{1,2,4,5},{2,3,5,6},{3,6} },
{ {4,7},{4,5,7,8},{5,6,8,9},{6,9} },
{ {7},{7,8},{8,9},{9} }
};
package zoj;import java.util.HashSet;import java.util.Queue;import java.util.Scanner;import java.util.Set;import java.util.Stack;public class WindowPains_poj1585 {//用map存放邻接矩阵，map[i][j]=1表示，j窗口在i窗口上面，不一定紧挨着static int map[][] ;//比如在地图中的[2][2]位置，可以放置{1,2,4,5},如果这个地方显示的是5，则说明 5覆盖了1,2,4static int dir[][][]= { //每个位置可以放置哪些窗口{ {1},{1,2},{2,3},{3} },{ {1,4},{1,2,4,5},{2,3,5,6},{3,6} },{ {4,7},{4,5,7,8},{5,6,8,9},{6,9} },{ {7},{7,8},{8,9},{9} }};static Set<Integer> set; //存储不重复static int degree[];public static int topoSort(){int n = set.size(); //当前窗口的个数Stack<Integer> stack = new Stack<Integer>();for(Integer index:set){ //先找到入度为0的节点if(degree[index] == 0)stack.push(index);}int cnt = 0;while( !stack.empty() ){cnt ++;int cur = stack.pop();for(int i=0; i<9; i++){if(map[cur][i] == 1){degree[i] --;if(degree[i] == 0){stack.push(i);}}}}if(cnt == n) //如果可以用拓扑排序 排好所有窗口return 1;return 0;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);set = new HashSet<Integer>();while(scan.hasNextLine()){String str = scan.next();if(str.endsWith("INPUT"))break;map = new int[10][10]; degree = new int[9];for(int i=0; i<4; i++){for(int j=0; j<4; j++){int temp = scan.nextInt();set.add(temp - 1);for(int k=0; k<dir[i][j].length; k++){if( map[dir[i][j][k] -1][temp-1] == 0 && dir[i][j][k] != temp) degree[temp-1] ++; //该节点的入度加1map[dir[i][j][k] -1][temp-1] = 1; //存入邻接矩阵}}}scan.next(); //读取最后的一行int ans = topoSort();if(ans == 1)System.out.println("THESE WINDOWS ARE CLEAN");elseSystem.out.println("THESE WINDOWS ARE BROKEN");}}}