白駿アルゴリズム1926号:図
13498 ワード
リンク
https://www.acmicpc.net/problem/1926
質問する
ある大きな画用紙に絵が描かれている場合は、その絵の個数と、その中で最も幅の大きい絵を印刷してください.ただし、図を1で接続した図と定義する.横または縦に接続されているのは接続されており、対角線に接続されているのは脱落した画像です.図の幅は、図に含まれる1の個数である.
入力
1行目には、グラフ紙の縦寸法n(1≦n≦500)と横寸法m(1≦m≦500)が順次与えられる.2行目からn+1行目に画像の情報が供給される.(ただし、図中の情報は0と1が空、0が未着色部分、1が着色部分)
しゅつりょく
1行目は画像の個数を出力し、2行目はその中で最も広い画像の幅を出力する.しかし、1枚の絵がなければ、最も広い絵の幅は0です.
入力と出力の例
解法
プールコード（C言語）
#include <stdio.h>
#define MAX 500
int graph[MAX][MAX];
int visited[MAX][MAX];
int components;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int answer[MAX];
int floodfill(int x, int y)
{
visited[x][y] = 1;
int newX, newY;
components++; // 연결 요소의 개수 증가
for (int i = 0; i < 4; i++)
{
newX = x + dx[i];
newY = y + dy[i];
if (0 <= newX && newX < MAX && 0 <= newY && newY < MAX)
{
if (visited[newX][newY] == 0 && graph[newX][newY] == 1)
{
floodfill(newX, newY);
}
}
}
return components;
}
int main()
{
int n, m, i = 0, j = 0, count = 0;
int max = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
scanf("%d", &graph[i][j]);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j] == 0 && graph[i][j] == 1)
{
components = 0;
answer[count] = floodfill(i, j);
count++;
}
}
}
printf("%d\n", count);
for (int i = 0; i < count; i++)
{
if (max < answer[i])
{
max = answer[i];
}
}
printf("%d", max);
return 0;
}Reference
この問題について(白駿アルゴリズム1926号:図), 我々は、より多くの情報をここで見つけました https://velog.io/@inwooleeme/백준-알고리즘-1926번-그림テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol