[백준 1113번] 수영장 만들기

문제 링크: 1113번 수영장 만들기

https://www.acmicpc.net/problem/1113

 

int rows, cols;
int[,] board;
int[,] filled;
int[] dr = { 0, 0, 1, -1 };
int[] dc = { 1, -1, 0, 0 };

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
string[] head = sr.ReadLine().Split();
rows = int.Parse(head[0]);
cols = int.Parse(head[1]);
board = new int[rows, cols];
filled = new int[rows, cols];
for (int i = 0; i < rows; i++)
{
    string line = sr.ReadLine();
    for (int j = 0; j < cols; j++)
    {
        board[i, j] = line[j] - '0';
    }
}

bool[,] visit = new bool[rows, cols];
bool apply;
List<(int, int)> list = new List<(int, int)>();

for (int level = 1; level <= 9; level++)
{
    Vinit();
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            apply = true;
            list.Clear();
            if (board[i, j] >= level || visit[i, j]) continue;
            Spread(i, j, level);
            if (apply)
            {
                foreach ((int, int) item in list)
                {
                    filled[item.Item1, item.Item2] = level;
                }
            }
        }
    }
}

int sum = 0;
for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        if (filled[i, j] < 1) continue;
        sum += filled[i, j] - board[i, j];
    }
}
System.Console.WriteLine(sum);

void Vinit()
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            visit[i, j] = false;
        }
    }
}

void Spread(int ir, int ic, int level)
{
    visit[ir, ic] = true;
    list.Add((ir, ic));
    
    for (int d = 0; d < 4; d++)
    {
        int nr = ir + dr[d];
        int nc = ic + dc[d];
        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols)
        {
            apply = false;
            continue;
        }
        if (board[nr, nc] >= level || visit[nr, nc])
        {
            continue;
        }
        Spread(nr, nc, level);
    }
}