#92597 (C#(csc)) No.307 最近色塗る問題多くない？

提出ソース

結果

問題	No.307 最近色塗る問題多くない？
ユーザー	14番
提出日時	2016-05-17 00:30:41
言語	C#(csc) (csc 3.9.0)
結果	TLE
実行時間	-
コード長	6,858 bytes
コンパイル時間	966 ms
コンパイル使用メモリ	111,744 KB
実行使用メモリ	45,824 KB
最終ジャッジ日時	2024-04-15 22:41:24
合計ジャッジ時間	17,725 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	36 ms 45,824 KB
testcase_01	AC	36 ms 19,584 KB
testcase_02	AC	36 ms 19,584 KB
testcase_03	AC	36 ms 19,328 KB
testcase_04	AC	46 ms 20,864 KB
testcase_05	AC	37 ms 19,584 KB
testcase_06	AC	37 ms 19,840 KB
testcase_07	AC	186 ms 25,088 KB
testcase_08	TLE	-
testcase_09	AC	1,373 ms 31,104 KB
testcase_10	AC	208 ms 39,040 KB
testcase_11	AC	1,129 ms 42,580 KB
testcase_12	AC	37 ms 19,456 KB
testcase_13	AC	89 ms 23,808 KB
testcase_14	AC	77 ms 23,680 KB
testcase_15	AC	126 ms 24,320 KB
testcase_16	AC	137 ms 24,448 KB
testcase_17	AC	2,800 ms 39,552 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.

ソースコード

raw source code

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();
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード