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

• 問題: No.307 最近色塗る問題多くない？
• ユーザー: 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

ファイルパターン	結果
other	AC * 17 TLE * 2 -- * 17

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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