글 읽기 - 반례부탁드립니다!

skesswswkk 4년 전 0

테케는 다 맞는데 틀렸습니다가 뜨네요 반례 부탁드립니다!

#include <iostream>//
#include <vector>
#include <set>
using namespace std;

int n, m;
char a[1001][1001]; //
int b[1000][1000];
bool check[1000][1000];
vector<int> v;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int dfs(int x, int y, int z) {
	b[x][y] = z;
	int ret = 1;
	check[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
			continue;
		}
		if (!check[nx][ny] && a[nx][ny] == '0') {//
			ret += dfs(nx, ny, z);
		}
	}
	return ret;
}

void solve() {
	// Flood-fill
	int z = 1;
	v.push_back(0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j]=='0' && !check[i][j]) {
				v.push_back(dfs(i, j, z));
				z += 1;
			}
		}
	}
	// Add sum to wall
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == '1') {
				set<int> s;
				for (int k = 0; k < 4; k++) {
					int ni = i + dx[k], nj = j + dy[k];
					if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
						continue;
					}
					s.insert(b[ni][nj]);
				}
				int sum = 0;//
				for (auto k : s) {//
					sum += v[k];
				}
				a[i][j] = (sum % 10) + 48 + 1;//
			}
		}
	}
	// Print
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << a[i][j];
		}
		cout << "\n";
	}
}

int main() {
	cin >> n >> m;//
	for (int i = 0; i < n; i++) {//
		cin >> a[i];
	}
	solve();
	return 0;
}

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

문제

문제

출처

ICPC

반례부탁드립니다!

skesswswkk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말