結果

問題 No.307 最近色塗る問題多くない？
ユーザー 14番14番
提出日時 2016-05-17 00:30:41
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 6,858 bytes
コンパイル時間 902 ms
コンパイル使用メモリ 116,524 KB
実行使用メモリ 60,076 KB
最終ジャッジ日時 2024-10-06 05:00:51
合計ジャッジ時間 17,353 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
60,076 KB
testcase_01 AC 34 ms
28,040 KB
testcase_02 AC 33 ms
25,520 KB
testcase_03 AC 34 ms
25,860 KB
testcase_04 AC 43 ms
25,580 KB
testcase_05 AC 35 ms
25,484 KB
testcase_06 AC 35 ms
27,648 KB
testcase_07 AC 180 ms
31,040 KB
testcase_08 TLE -
testcase_09 AC 1,260 ms
37,132 KB
testcase_10 AC 202 ms
47,008 KB
testcase_11 AC 1,059 ms
50,972 KB
testcase_12 AC 37 ms
25,360 KB
testcase_13 AC 82 ms
32,044 KB
testcase_14 AC 72 ms
29,672 KB
testcase_15 AC 120 ms
32,360 KB
testcase_16 AC 128 ms
28,580 KB
testcase_17 AC 2,953 ms
45,536 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
        int height = inpt[0];
        int width = inpt[1];
        this.map = new MapState[height, width];
        for(int i=0; i<height; i++) {
            inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
            for(int j=0; j<width; j++) {
                this.map[i,j] = new MapState(i, j, inpt[j]);
            }
        }
        // グループ分ける
        this.Grouping();
        int queryCount = int.Parse(Reader.ReadLine());
        for(int i=0; i<queryCount; i++) {
            inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
            this.Proc(inpt[0]-1, inpt[1]-1, inpt[2]);
        }
        if(Group.Count == 1) {
            for(int i=0; i<height; i++) {
                StringBuilder lin = new StringBuilder();
                for(int j=0; j<width; j++) {
                    lin.Append(" " + map[0,0].Color);
                }
                Console.WriteLine(lin.ToString().Substring(1));
            }
        } else {
            for(int i=0; i<height; i++) {
                StringBuilder lin = new StringBuilder();
                for(int j=0; j<width; j++) {
                    lin.Append(" " + map[i,j].Color);
                }
                Console.WriteLine(lin.ToString().Substring(1));
            }
            
        }
    }
    
    private void Proc(int r, int c, int newC) {
        if(this.Group.Count > 1 && map[r,c].Color == newC) {
            return;
        }
        if(this.Group.Count == 1) {
            map[0,0].Color = newC;
            return;
        }
        if(this.Group.Count == 2) {
            int last = this.Group.Keys.Last();
            int first = this.Group.Keys.First();
            this.Group[last].ForEach(a=>a.Group = first);
            this.Group[first].AddRange(this.Group[last]);
            this.Group.Remove(last);
            map[0,0].Col = newC;
            return;
        }
        Queue<TaskItem> task = new Queue<TaskItem>();
        this.Group[map[r,c].Group].ForEach((a)=>{
            a.Color = newC;
            task.Enqueue(new TaskItem(a.Row, a.Col, newC));
        });
        while (task.Count > 0)
        {
            TaskItem t = task.Dequeue();
            int groupIndex = map[t.Row,t.Col].Group;
            List<Pos> rin = this.GetRinsetsu(t.Row,t.Col);
            rin.ForEach((a)=>{
                if(map[a.Row, a.Col].Group != groupIndex) {
                    int margeIndex = map[a.Row, a.Col].Group;
                    this.Group[margeIndex].ForEach(b=>b.Group = groupIndex);
                    this.Group[groupIndex].AddRange(this.Group[margeIndex]);
                    this.Group.Remove(margeIndex);
                } 
            });
        }
    }
    
    private void Grouping() {
        Dictionary<int, List<MapState>> grp = new Dictionary<int, List<MapState>>();
        while (map.GetLength(0) * map.GetLength(1) > grp.Sum(a=>a.Value.Count()))
        {
            Queue<TaskItem> task = new Queue<TaskItem>();
            Pos target = new Pos(0,0);
            bool isFind = false;
            for(int i=0; i<map.GetLength(0); i++) {
                for(int j=0; j<map.GetLength(1); j++) {
                    if(map[i,j].Group < 0) {
                        target = new Pos(i,j);
                        isFind = true;
                        break;
                    }
                }
                if(isFind) {
                    break;
                }
            }
            task.Enqueue(new TaskItem(target.Row, target.Col ,map[target.Row, target.Col].Color));
            int groupInde = grp.Count;
            map[target.Row,target.Col].Group = groupInde;
            grp.Add(groupInde,  new List<MapState>());
            grp[groupInde].Add(map[target.Row,target.Col]);
            while (task.Count > 0)
            {
                TaskItem t = task.Dequeue();
                List<Pos> nextPosList = this.GetRinsetsu(t.Row,t.Col);
                
                nextPosList.ForEach((a)=>{
                    if(map[a.Row, a.Col].Color == t.NewColor && map[a.Row, a.Col].Group < 0) {
                        map[a.Row, a.Col].Group = groupInde;
                        task.Enqueue(new TaskItem(a.Row, a.Col, map[a.Row, a.Col].Color));
                        grp[groupInde].Add(map[a.Row, a.Col]);
                    }
                });
            }
            
        }
        this.Group = grp;
    }
    private Dictionary<int, List<MapState>> Group = new Dictionary<int, List<MapState>>();
    
    private List<Pos> GetRinsetsu(int r, int c) {
        List<Pos> ret = new List<Pos>();

        if(r > 0) {
            ret.Add(new Pos(r-1, c));
        }
        if(r < this.map.GetLength(0) - 1) {
            ret.Add(new Pos(r+1, c));
        }
        if(c > 0) {
            ret.Add(new Pos(r,c-1));
        }
        if(c < this.map.GetLength(1)-1) {
            ret.Add(new Pos(r, c+1));
        }
        return ret;
    }
    public struct Pos {
        public int Row;
        public int Col;
        public Pos(int r, int c) {
            this.Row = r;
            this.Col = c;
        }
    }
    
    private MapState[,] map;
    public class TaskItem {
        public int Col;
        public int Row;
        public int NewColor;
        public TaskItem(int r, int c, int newColor) {
            this.Row = r;
            this.Col = c;
            this.NewColor = newColor;
        }
    }
    
    public class MapState {
        public int Col;
        public int Row;
        public int Color;
        public int Group = -1;
        
        public MapState(int r, int c, int color) {
            this.Row = r;
            this.Col = c;
            this.Color = color;
        }
    }
    
    
    

    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"



8 8
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
12
3 7 1
4 3 0
7 2 0
5 7 1
5 3 1
3 3 0
7 2 1
8 7 0
2 7 0
8 2 1
2 1 0
6 3 1



 
";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0