[21327][伯俊/BOJ]7576号トマト

2202 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する



にゅうしゅつりょく



に答える


箱には熟したトマトと未熟なトマトが入っています.完熟したトマトは1日で上下左右に存在する完熟していないトマトに影響し、完熟した状態になります.
これは問題で、箱の中に成熟したトマトと未成熟のトマトがある場合、すべてのトマトが成熟する最低日数を見つけなければなりません.
熟成トマトは隣接トマトに影響を与える問題であり,BFSによって問題を解決することができ,すべてのトマトの熟成の最小日数は距離を求める方法で解決できる.
この問題は、1つの始点ではなく複数の始点が存在し、各始点が同時に実行される必要があります.したがって
  • は、まずすべての開始点を見つけてキューに入れます.
  • 距離を求めるために,未熟トマトの距離値を−1に初期化した.
  • 元素のdist値が0より大きい場合、トマトまたはトマトを通過していない格子を一度に処理することができる.
  • の最小日数を求める場合、未成熟トマト(dist[i][j]=−1)が存在する場合、−1が出力される.

    • コード#コード#

    #include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 1002

int board[SIZE][SIZE];
int dist[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

// 거리 구하는 방식으로 최대 거리를 찾는다 
// 최대 거리가 최소 날짜가 됨

int main()
{
	int m, n; // m은 열, n은 행
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	queue<pair<int, int>> Q;
	
	// 여러개의 시작점이 동시에 실행
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] == 1) // 익은 토마토 -> 시작점
				Q.push({ i,j });
			if (board[i][j] == 0) // 익지않은 토마토라면
				dist[i][j] = -1; // -1로 초기화
		}
	}
	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; ++dir)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0) continue; // 이미 지나간 토마토나 토마토가 없는 칸도 커버가능
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx, ny });
		}
	}

	int mx = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (dist[i][j] == -1) // 익지 않은 토마토가 있다면
			{
				cout << -1;
				return 0; // 프로그램 종료
			}
			mx = max(mx, dist[i][j]);
		}
	}
	cout << mx;
}
    中央揃え[Webデザイン]
    1日1時T-SQL:ストアド・プロシージャ・テキストのエクスポート