結果

問題 No.43 野球の試合
コンテスト
ユーザー 14番
提出日時 2016-04-04 23:04:27
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 226 ms / 5,000 ms
コード長 3,737 bytes
コンパイル時間 1,062 ms
コンパイル使用メモリ 111,908 KB
実行使用メモリ 30,116 KB
最終ジャッジ日時 2024-10-04 01:03:56
合計ジャッジ時間 2,710 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff #
raw source code 

using System;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public void Proc(){
        
        Reader.IsDebug = false;
        
        int teamCount = int.Parse(Reader.ReadLine());
        
        char[,] map = new char[teamCount, teamCount];
        
        for(int i=0; i<teamCount; i++) {
            string temp = Reader.ReadLine();
            for(int j=0; j<teamCount; j++) {
                map[i,j] = temp[j];
            }
        }
        int ans = GetAns(0,1,map);
        Console.WriteLine(ans);
    }
    
    private int GetAns(int row, int col, char[,] target) {
        if(row < target.GetLength(0) - 1 && col < target.GetLength(1)) {
            int ans = int.MaxValue;
            for(int i=row; i<target.GetLength(0)-1; i++) {
                for(int j=i+1; j<target.GetLength(1); j++) {
                    if(i==row && j < col) {
                        continue;
                    }
                    if(target[i,j] == '-') {
                        int nextRow = i;
                        int nextCol = j + 1;
                        if(nextCol >= target.GetLength(1)) {
                            nextRow++;
                            nextCol = nextRow + 1;
                        }
                        char[,] work = this.CloneCopy(target);
                        work[i,j] = 'o';
                        work[j,i] = 'x';
                        ans = Math.Min(this.GetAns(nextRow, nextCol, work), ans);
                        work[i, j] = 'x';
                        work[j, i] = 'o'; 
                        ans = Math.Min(this.GetAns(nextRow, nextCol, work), ans);
                        return ans;
                    }
                }
            }
        }
        
        Dictionary<int, List<int>> winCount = new Dictionary<int, List<int>>();
        List<int> keyList = new List<int>();
        for(int i=0; i<target.GetLength(0); i++) {
            int num = 0;
            for(int j=0; j<target.GetLength(1); j++) {
                if(target[i,j]=='o') {
                    num++;
                }
            }
            if(!winCount.ContainsKey(num)) {
                winCount.Add(num, new List<int>());
                keyList.Add(num);
            } 
            winCount[num].Add(i);
        }
        keyList.Sort();
        keyList.Reverse();
        for(int i=0; i<keyList.Count; i++) {
            int key = keyList[i];
            if(winCount[key].Contains(0)) {
                return i+1;
            }
        }
        return target.GetLength(0);
    }
    
    private char[,] CloneCopy(char[,] src) {
        char[,] ret = new char[src.GetLength(0), src.GetLength(1)];
        for(int i=0; i<src.GetLength(0); i++) {
            for(int j=0; j<src.GetLength(1); j++) {
                ret[i,j] = src[i,j];
            }
        }
        return ret;
    }
    
    
    public static void Main(string[] args)
    {
        Program prg = new Program();
        prg.Proc();
    }
}

class Reader
{
    public static bool IsDebug = true;
    
    private static System.IO.StringReader sr;
    
    public static string ReadLine() {
        if(IsDebug) {
            if(sr == null) {
                sr = new System.IO.StringReader(initStr.Trim());
            }
            return sr.ReadLine();
        } else {
            return Console.ReadLine();
        }
    }
    
    public static int[] GetInt(char delimiter = ' ') {
        string[] inpt = ReadLine().Split(delimiter);
        int[] ret = new int[inpt.Length];
        for(int i=0; i<inpt.Length; i++) {
            ret[i] = int.Parse(inpt[i]);
        }
        return ret;
    }
    
    private static string initStr = @"


4
#-xx
-#x-
oo#-
o--#



";
}
0