1486 Sorting Slides

「1486 Sorting Slides」の編集履歴（バックアップ）一覧はこちら

「1486 Sorting Slides」(2006/05/14 (日) 00:22:36) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1485 Sotring Slides
**解答例
 import java.util.*;
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int casenum = 0;
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             casenum++;
             
             Rectangle[] rs = new Rectangle[n];
             for(int i=0;i<n;i++){
                 rs[i] = new Rectangle(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
             }
             
             int[] xs = new int[n];
             int[] ys = new int[n];
             for(int i=0;i<n;i++){
                 xs[i] = sc.nextInt();
                 ys[i] = sc.nextInt();
             }
             
             boolean table[][] = new boolean[n][n];
             for(int i=0;i<n;i++){
                 for(int j=0;j<n;j++){
                     table[i][j] = rs[i].in(xs[j], ys[j]);
                 }
             }
             
             boolean determined_i[] = new boolean[n];
             boolean determined_j[] = new boolean[n];
             int ans[] = new int[n];
             Arrays.fill(determined_i, false);
             Arrays.fill(determined_j, false);
             Arrays.fill(ans, -1);
             
             while(true){
                 boolean end = true;
                 for(int i=0;i<n;i++){
                     if(determined_i[i]) continue;
                     int cnt = 0;
                     int lastj = -1;
                     for(int j=0;j<n;j++){
                         if(determined_j[j]) continue;
                         if(table[i][j]){
                             lastj = j;
                             cnt++;
                         }
                     }
                     if(cnt==1){
                         ans[i] = lastj;
                         determined_i[i] = true;
                         determined_j[lastj] = true;
                         end = false;
                     }
                 }
                 for(int j=0;j<n;j++){
                     if(determined_j[j]) continue;
                     int cnt = 0;
                     int lasti = -1;
                     for(int i=0;i<n;i++){
                         if(determined_i[i]) continue;
                         if(table[i][j]){
                             lasti = i;
                             cnt++;
                         }
                     }
                     if(cnt==1){
                         ans[lasti] = j;
                         determined_i[lasti] = true;
                         determined_j[j] = true;
                         end = false;
                     }
                 }
                 if(end) break;
             }
             
             boolean none = true;
             for(int i=0;i<n;i++)
                 if(determined_i[i]) none = false;
             
             System.out.printf("Heap %d\r\n",casenum);
             if(none){
                 System.out.println("none");
             }
             else{
                 for(int i=0;i<n;i++){
                     if(determined_i[i]) System.out.printf("(%c,%d) ", 'A'+i, 1+ans[i]);
                 }
                 System.out.println();
             }
             System.out.println();
         }
     }
 }
 
 class Rectangle{
     int xmin;
     int xmax;
     int ymin;
     int ymax;
     public Rectangle(int xmin, int xmax, int ymin, int ymax) {
         super();
         // TODO Auto-generated constructor stub
         this.xmin = xmin;
         this.xmax = xmax;
         this.ymin = ymin;
         this.ymax = ymax;
     }
     public boolean in(int x, int y){
         return (xmin<x && x<xmax && ymin<y && y<ymax);
     }
 }