Google Code Jam 2009 B C#でといてみた

長いのが悔しい。

けどわかりやすい再帰。

class B

{

public enum Dir

{

Nothing,

North,

West,

East,

South

}

public class Cell

{

public Dir Direction;

public int Label;

public int Alt;

}

int H;

int W;

int T;

public void Run()

{

List res = new List();

int line = 0;

var ss = File.ReadAllLines("B-large.in");

T = ss[0].ToInt();

line++;

for (int i = 0; i <>

{

res.Add("Case #{0}:".FormatWith(i + 1));

int maxlabel = 1;

var s = ss[line].Split(' ');

line++;

H = s[0].ToInt();

W = s[1].ToInt();

var map = new Cell[H, W];

for (int h = 0; h <>

{

for (int w = 0; w <>

{

map[h, w] = new Cell();

}

}

for (int h = 0; h <>

{

var m = ss[line].Split(' ');

line++;

for (int w = 0; w <>

{

map[h, w].Alt = m[w].ToInt();

}

}

for (int h = 0; h <>

{

for (int w = 0; w <>

{

Dir dir;

var jibun = map[h, w].Alt;

var na = h == 0 ? int.MaxValue : map[h - 1, w].Alt;

var wa = w == 0 ? int.MaxValue : map[h, w - 1].Alt;

var ea = w == W - 1 ? int.MaxValue : map[h, w + 1].Alt;

var sa = h == H - 1 ? int.MaxValue : map[h + 1, w].Alt;

var min = new[] { jibun, na, wa, ea, sa }.Min();

if (jibun == min)

dir = Dir.Nothing;

else if (na == min)

dir = Dir.North;

else if (wa == min)

dir = Dir.West;

else if (ea == min)

dir = Dir.East;

else

dir = Dir.South;

map[h, w].Direction = dir;

}

}

for (int h = 0; h <>

{

for (int w = 0; w <>

{

if (map[h, w].Label == 0)

{

Check(map, h, w, maxlabel);

maxlabel++;

}

}

}

for (int h = 0; h <>

{

var r = new string[W];

for (int w = 0; w <>

{

r[w] = ((char)(map[h, w].Label + ((int)'a') - 1)).ToString();

}

res.Add(r.Join(" "));

}

}

File.WriteAllLines("Ans.txt", res.ToArray());

Console.Write(res.ToArray().Join(Environment.NewLine));

Console.ReadKey();

}

public void Check(Cell[,] map, int h, int w, int label)

{

if (map[h, w].Label > 0)

return;

map[h, w].Label = label;

if (h > 0 && (map[h,w].Direction == Dir.North || map[h - 1, w].Direction == Dir.South))

Check(map, h - 1, w, label);

if (w > 0 && (map[h, w].Direction == Dir.West || map[h, w - 1].Direction == Dir.East))

Check(map, h, w - 1, label);

if (h + 1 < direction ="=" direction ="=">

Check(map, h + 1, w, label);

if (w + 1 < direction ="=" direction ="=">

Check(map, h, w + 1, label);

}

}