結果

問題 No.640 76本のトロンボーン
コンテスト
ユーザー バカらっく
提出日時 2018-01-27 23:56:17
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 3,349 bytes
コンパイル時間 2,174 ms
コンパイル使用メモリ 108,928 KB
実行使用メモリ 848,512 KB
最終ジャッジ日時 2024-12-29 07:09:32
合計ジャッジ時間 20,661 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 MLE * 1
other AC * 8 TLE * 6 MLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        this.N = int.Parse(Reader.ReadLine());
        bool[][] map = new bool[this.N][];
        for (int i = 0; i < this.N; i++) {
            map[i] = Reader.ReadLine().Select(a => a == '.').ToArray();
        }
        int ans = GetAns(0, map, GetKey(0, map));
        Console.WriteLine(ans);
    }

    private Dictionary<string, int> dic = new Dictionary<string, int>();
    private int GetAns(int idx, bool[][] map, string key) {
        if(idx>=this.N*this.N) {
            return 0;
        }
        int r = idx / this.N;
        int c = idx % this.N;
        if(!map[r][c]) {
            return GetAns(idx + 1, map, key.Substring(1));
        }
        if(dic.ContainsKey(key)) {
            return dic[key];
        }
        int ans = 0;
        if(r+(this.N-2)<this.N) {
            bool canSet = true;
            for (int i = r; i < r + this.N - 1; i++) {
                if(!map[i][c]) {
                    canSet = false;
                    break;
                }
            }
            if(canSet) {
                for (int i = r; i < r + this.N - 1; i++) {
                    map[i][c] = false;
                }
                string newKey = GetKey(idx + 1, map);
                ans = Math.Max(ans, GetAns(idx + 1, map, newKey)+1);
                for (int i = r; i < r + this.N - 1; i++)
                {
                    map[i][c] = true;;
                }
            }
        }
        if(c+(this.N-2)<this.N) {
            bool canSet = true;
            for (int i = c; i < c + this.N - 1; i++) {
                if(!map[r][i]) {
                    canSet = false;
                    break;
                }
            }
            if (canSet)
            {
                for (int i = c; i < c + this.N - 1; i++)
                {
                    map[r][i] = false;
                }
                string newKey = GetKey(idx + 1, map);
                ans = Math.Max(ans, GetAns(idx + 1, map, newKey)+1);
                for (int i = c; i < c + this.N - 1; i++)
                {
                    map[r][i] = true;;
                }
            }
        }
        ans = Math.Max(ans, GetAns(idx + 1, map, key.Substring(1)));
        dic[key] = ans;
        return ans;
    }

    private string GetKey(int idx, bool[][] map) {
        String ret = string.Join("", map.Select(a => string.Join("", a.Select(b => b ? "1" : "0"))));
        return ret.Substring(idx);
    }

    private int N;

    public class Reader
    {
        private static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"



5
...#.
..#.#
.....
#....
##..#





";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}
0