トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.402 最も海から遠い場所
■■■問題■■■
縦H、横Wのサイズの地図があります。地図には、その場所が陸地か海かの情報が与えられます。
地図外の領域はすべて海です。
海からのチェビシェフ距離が最も遠い場所のその距離を求めてください。
1.チェビシェフ距離とは、隣接する8マスに移動できる (将棋の王将のような)コマが、
任意のマスから任意のマスに移動するのにかかる最小移動回数ととらえてもらって構いません。
2.ある陸と海との距離は、ある陸と全ての海とのチェビシェフ距離の内、最小の値です。
■■■入力■■■
H W
S1
S2
・
・
SH
一行目に地図のサイズを示すHとWがスペース区切りで与えられます。
二行目以降のH行に地図を表すW文字の文字列が与えられます。
"#"は陸、"."は海を表します。陸は必ず一つ以上存在します。
HとWは整数、1 <= H,W <= 3000
Siは"#"と"."からなるW文字の文字列
■■■出力■■■
海からのチェビシェフ距離が最も遠い場所のその距離を出力してください。
■■■サンプルケースのイメージ■■■
■入出力例1のイメージ■
緑色の部分を陸、水色の部分を海として、
それぞれの陸地の海からのチェビシェフ距離は下図のようになります。
チェビシェフ距離が最も大きい場所のその値は3なので、それを出力します。
■入出力例2のイメージ■
島の中に海が存在する場合があります。
また、地図の範囲外は全て海であることに注意してください。
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("8 8");
WillReturn.Add(".#..#...");
WillReturn.Add(".######.");
WillReturn.Add("#####...");
WillReturn.Add("#####.#.");
WillReturn.Add("########");
WillReturn.Add("######.#");
WillReturn.Add("#####...");
WillReturn.Add("...####.");
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("7 7");
WillReturn.Add("#######");
WillReturn.Add("#######");
WillReturn.Add("#######");
WillReturn.Add("#######");
WillReturn.Add("#.#####");
WillReturn.Add("#..####");
WillReturn.Add("#######");
//3
}
else if (InputPattern == "Input3") {
List<string> P = WillReturn;
P.Add("60 60");
P.Add("............................................................");
P.Add("............................................................");
P.Add("........................................#...............##..");
P.Add(".......................................####............##...");
P.Add(".........................................##...........##....");
P.Add(".........................................###........#.......");
P.Add(".........................................#####...#..#.......");
P.Add(".........................................#########....#.....");
P.Add("........................................###########.........");
P.Add("........................................#############.......");
P.Add(".....................................##.##########..........");
P.Add("......................................#########.............");
P.Add(".....................................#########..............");
P.Add("....................................##.#...###..............");
P.Add("...................................###.......#..............");
P.Add(".....................................###....................");
P.Add(".....................................#......................");
P.Add(".......................................##...................");
P.Add("......................................#.#...................");
P.Add(".....................................####...................");
P.Add(".....................................####...................");
P.Add(".....................................#####..................");
P.Add(".....................................######.................");
P.Add(".....................................######.................");
P.Add(".....................................######.................");
P.Add(".....................................#####..................");
P.Add("....................................#####...................");
P.Add("....................................#####...................");
P.Add("....................................######..................");
P.Add("...................................#####....................");
P.Add("................................#.######....................");
P.Add(".................................#######....................");
P.Add("............................#...########....................");
P.Add("............................#.##########....................");
P.Add("...........................############.....................");
P.Add("...........................############.....................");
P.Add("..........................#############.....................");
P.Add(".........................###############....................");
P.Add("....................###..##############.....................");
P.Add("...............#####################.##.....................");
P.Add("..............###################.#..#......................");
P.Add(".....#......###############.####..#.........................");
P.Add("..........########......###.................................");
P.Add("..........####....##.#.#####................................");
P.Add("......#.##...#.######..###..................................");
P.Add(".....##.####...######..##...................................");
P.Add("......######..####.#........................................");
P.Add("...#...######.###...........................................");
P.Add("......##.####..#............................................");
P.Add(".......#.###................................................");
P.Add("........####................................................");
P.Add(".......####.................................................");
P.Add(".......####.................................................");
P.Add(".......#.##.................................................");
P.Add("............................................................");
P.Add("..........#.................................................");
P.Add("........#.#.................................................");
P.Add("............................................................");
P.Add("............................................................");
P.Add("............................................................");
//4
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static int UB_X;
static int UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
int H = wkArr[0];
int W = wkArr[1];
UB_X = W - 1;
UB_Y = H - 1;
char[,] BanArr = new char[UB_X + 1, UB_Y + 1];
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
BanArr[LoopX, LoopY] = InputList[LoopY + 1][LoopX];
}
}
int[,] CntArr = new int[UB_X + 1, UB_Y + 1];
Func<int, int, int> wkFunc = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return 0;
if (pY < 0 || UB_Y < pY) return 0;
return CntArr[pX, pY];
};
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (BanArr[LoopX, LoopY] == '.')
CntArr[LoopX, LoopY] = 0;
else {
int Cnt1 = wkFunc(LoopX - 1, LoopY - 1);
int Cnt2 = wkFunc(LoopX, LoopY - 1);
int Cnt3 = wkFunc(LoopX - 1, LoopY);
int wkMin = Math.Min(Cnt1, Cnt2);
wkMin = Math.Min(wkMin, Cnt3);
CntArr[LoopX, LoopY] = wkMin + 1;
}
}
}
int MaxSeihoukeiLength = CntArr.Cast<int>().Max();
if (MaxSeihoukeiLength % 2 == 0) Console.WriteLine(MaxSeihoukeiLength / 2);
else Console.WriteLine(MaxSeihoukeiLength / 2 + 1);
}
}
解説
最大の正方形を求めて、その1辺の長さ / 2 の端数切り上げ
を解としてます。
最大の正方形は、下記のロジックで、2次元配列を順に走査して求めてます。
●海なら0をセット
●陸なら、(左、左上、上の3つの座標の中での最小値)+1をセット