結果

問題 No.43 野球の試合
ユーザー threepipes_s
提出日時 2014-11-25 00:45:38
言語 Java
(openjdk 23)
結果
AC  
実行時間 183 ms / 5,000 ms
コード長 4,007 bytes
コンパイル時間 3,119 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 47,572 KB
最終ジャッジ日時 2025-01-02 21:17:58
合計ジャッジ時間 3,997 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.TreeSet;
public class Main {
    public static int w;
    public static int k;
    public static int n;
//  public static int[][] dp;
    public static int[] a;
    public static int[] b;
    public static List<double[]> list = new ArrayList<double[]>();
    public static TreeSet<Integer> set = new TreeSet<Integer>();
//  public static PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    public static void main(String[] args) throws NumberFormatException, IOException{
        ContestScanner in = new ContestScanner();
        n = in.nextInt();
        int[][] s = new int[n][n];
        String line;
        int rest = 0;
        for(int i=0; i<n; i++){
            line = in.nextToken();
            for(int j=0; j<n; j++){
                char c = line.charAt(j);
                if(c == '#') s[i][j] = 8;
                else if(c == '-'){
                    s[i][j] = 0;
                    rest++;
                }
                else if(c == 'o') s[i][j] = 1;
                else s[i][j] = 2;
            }
        }
        rest /= 2;
//      for(int i=0; i<n; i++){
//          if(s[0][i] == 0){
//              s[0][i] = 1;
//              s[i][0] = 2;
//              rest--;
//          }
//      }
        
        System.out.println(dfs(rest, s));
        
    }
    
    public static int dfs(int rest, int[][] buttle){
//      System.err.println("rest:"+rest);
        if(rest == 0){
            int count = 0;
//          int[] rank = new int[n];
            for(int i=n-1; i>=0; i--){
                count = 0;
                for(int j=0; j<n; j++){
                    count += buttle[i][j] == 1 ? 1 : 0;
//                  System.err.print(buttle[i][j]);
                }
//              System.err.println();
                set.add(count);
                
            }
            int i = 0;
            while(set.pollLast() != count) i++;
            set = new TreeSet<Integer>();
//          System.err.println(i);
//          System.err.println();
            return i+1;
        }else{
            int[][] copy = new int[n][n];
            boolean changed = false;
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    copy[i][j] = buttle[i][j];
                }
            }
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(!changed && buttle[i][j] == 0){
                        changed = true;
                        copy[i][j] = 1;
                        copy[j][i] = 2;
                        buttle[i][j] = 2;
                        buttle[j][i] = 1;
                    }
                }
            }
            
            return Math.min(dfs(rest-1, copy), dfs(rest-1, buttle));
            
        }
    }
    
}
class Node{
    int id;
    List<Node> edge = new ArrayList<Node>();
    public Node(int id){
        this.id = id;
    }
    public void createEdge(Node node){
        edge.add(node);
    }
}
class MyMath{
    public static long fact(long n){
        long res = 1;
        while(n > 0){
            res *= n--;
        }
        return res;
    }
    public static long[][] pascalT(int n){
        long[][] tri = new long[n][];
        for(int i=0; i<n; i++){
            tri[i] = new long[i+1];
            for(int j=0; j<i+1; j++){
                if(j == 0 || j == i){
                    tri[i][j] = 1;
                }else{
                    tri[i][j] = tri[i-1][j-1] + tri[i-1][j];
                }
            }
        }
        return tri;
    }
}
class MyComp implements Comparator<Integer>{
    public int compare(Integer arg0, Integer arg1) {
        return arg0 - arg1;
    }
}
//
//class MyCompB implements Comparator<int[]>{
//  public int compare(int[] arg0, int[] arg1) {
//      return arg0[1] - arg1[1];
//  }
//}
class ContestScanner{
    private BufferedReader reader;
    private String[] line;
    private int idx;
    public ContestScanner() throws FileNotFoundException{
        reader = new BufferedReader(new InputStreamReader(System.in));
    }
    
    public String nextToken() throws IOException{
        if(line == null || line.length <= idx){
            line = reader.readLine().trim().split(" ");
            idx = 0;
        }
        return line[idx++];
    }
    
    public long nextLong() throws IOException, NumberFormatException{
        return Long.parseLong(nextToken());
    }
    
    public int nextInt() throws NumberFormatException, IOException{
        return (int)nextLong();
    }
    
    public double nextDouble() throws NumberFormatException, IOException{
        return Double.parseDouble(nextToken());
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0