글 읽기 - 여기서 어떻게 수정해야 시간을 더 단축시킬 수 있을까요?

dkxm99 3년 전 0

c++ bfs 이용해서 풀었습니다.

#include <iostream>
#include <queue>
#include <cstring>
#define MAX (1000+5)

using namespace std;

int map[MAX][MAX];
bool visited[MAX][MAX];
int Move[MAX * MAX];
int m, n, cnt;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int b, int a) {
	queue<pair<int, int>>q;
	visited[b][a] = true;
	q.push(make_pair(b, a));
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (map[ny][nx] == 0 && !visited[ny][nx]) {
				visited[ny][nx] = true;
				Move[cnt]++;
				q.push(make_pair(ny, nx));
			}
		}
	}
	map[b][a] = Move[cnt] + 1;
	map[b][a] = map[b][a] % 10;
}

int main() {
	scanf("%d %d", &m, &n);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				cnt++;
				bfs(i, j);
				memset(visited, 0, sizeof(visited));
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d", map[i][j]);
		}
		printf("\n");
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

여기서 어떻게 수정해야 시간을 더 단축시킬 수 있을까요?

dkxm99 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말