代码
import java.io.*;
import java.util.*;
//区间类
class Segment{
int l,r;
public Segment(int a,int b){
this.l = Math.min(a,b);
this.r = Math.max(a,b);
}
}
class Main{
//行:该行合并后的区间集合
public static HashMap<Integer,ArrayList<Segment>> afterMergeRowsMap = new HashMap();
//列:该列合并后的区间集合。
public static HashMap<Integer,ArrayList<Segment>> afterMergecolsMap = new HashMap();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
HashMap<Integer,ArrayList<Segment>> rowMaps = new HashMap();//行:该行的区间集合
HashMap<Integer,ArrayList<Segment>> colMaps = new HashMap();//列:该列的区间集合
while(n-->0){
String[] strs = br.readLine().split(" ");
if(strs[0].equals(strs[2])){//读取行区间
int row = Integer.parseInt(strs[0]);
if(rowMaps.containsKey(row)){
ArrayList<Segment> t = rowMaps.get(row);
t.add(new Segment(Integer.parseInt(strs[1]),Integer.parseInt(strs[3])));
}else{
ArrayList<Segment> t = new ArrayList();
t.add(new Segment(Integer.parseInt(strs[1]),Integer.parseInt(strs[3])));
rowMaps.put(row,t);
}
}else{//读取列区间
int col = Integer.parseInt(strs[1]);
if(colMaps.containsKey(col)){
ArrayList<Segment> t = colMaps.get(col);
t.add(new Segment(Integer.parseInt(strs[0]),Integer.parseInt(strs[2])));
}else{
ArrayList<Segment> t = new ArrayList();
t.add(new Segment(Integer.parseInt(strs[0]),Integer.parseInt(strs[2])));
colMaps.put(col,t);
}
}
}
long res = 0; //最终的计数
res +=segmentsMerge("row",rowMaps); //行区间的染色格子总数
res +=segmentsMerge("col",colMaps); //列区间的染色格子总数
//把行列区间之间有重复的格子去掉
for(Map.Entry<Integer,ArrayList<Segment>> a : afterMergeRowsMap.entrySet()){
for(Segment i : a.getValue()){ //遍历每个合并后行区间
for(Map.Entry<Integer,ArrayList<Segment>> b : afterMergecolsMap.entrySet()){
for(Segment j: b.getValue()){//遍历每个合并后的列区间
if(a.getKey()>=j.l&&a.getKey()<=j.r&&b.getKey()>=i.l&&b.getKey()<=i.r){//行列区间有交叉的话,就说明有一个格子要去重。
res--;
}
}
}
}
}
System.out.print(res);
}
//区间合并方法。在合并区间的过程中顺便完成染色格子的计算,并返回。
public static long segmentsMerge(String s,HashMap<Integer,ArrayList<Segment>> map){
long res = 0;
for(Map.Entry<Integer,ArrayList<Segment>> a : map.entrySet()){
ArrayList<Segment> u = new ArrayList();
ArrayList<Segment> t = a.getValue();
Collections.sort(t,(p,q)->p.l-q.l);//先对该行/列 区间集合排序
int cul_l = t.get(0).l,cul_r = t.get(0).r;
for(int i=1;i<t.size();i++){
Segment b = t.get(i);
if(b.l>cul_r){
//该行/列 合并后的区间放到新的集合中。
u.add(new Segment(cul_l,cul_r));
//计算独立区间的染色格子
res+=(cul_r-cul_l+1);
//修改区间
cul_l = b.l;
cul_r = b.r;
}else{
cul_r = Math.max(cul_r,b.r);
}
}
res+=(cul_r-cul_l+1);//最后一个独立区间别忘了加上
u.add(new Segment(cul_l,cul_r));//最后一个独立区间别忘了加上
if(s.equals("row")){
afterMergeRowsMap.put(a.getKey(),u); //合并完成的放到新的map中。便于后续计算去重。
}else{
afterMergecolsMap.put(a.getKey(),u); //合并完成的放到新的map中。便于后续计算去重。
}
}
return res;
}
}
评析
思想:二维区间太复杂,因此这里看成 提供了一些行区间,一些列区间,我们分别通过区间合并的方法去处理行区间,列区间,这样可以分别 计算出行这一个维度染色的格子数,列这个维度染色的格子数。 最后我们再去遍历行区间与列区间,去一下行列区间交叉的格子。
需要注意的有:计算行列区间交叉的格子的时候一定要用合并后的行列区间计算,否则会多去重的。
segmentsMerge() 方法其实是一维的区间合并题( 区间合并 )。只不过合并的时候再顺便计算一些其他值而已。