글 읽기 - 예제는 잘 나오는데 틀렸다고 뜨네요ㅠㅠ

vire3064 4년 전 0

예제는 잘 나오는데 10%도 못가서 틀렸다고 뜨네요..ㅠ

반례나 문제점 알 수 있을까요? ㅠㅠ

#pragma warning(disable : 4996)
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

#define endl '\n'

typedef long long ll;

const int INF = 987654321;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };

struct INFO {
	int y, x;
	INFO(int y = 0, int x = 0) : y(y), x(x){}
};

int map[100][10];
bool visited[100][10];
int n, k;
bool flag;

// remove function
void boom(int sy, int sx) {
	int tmp[100][10] = { 0, };
	bool visit[100][10] = { 0, };
	// copy
	for (int y = 0; y < 100; ++y) {
		for (int x = 0; x < 10; ++x) {
			tmp[y][x] = map[y][x];
		}
	}
	queue<INFO> q;
	q.push({ sy,sx });
	visit[sy][sx] = 1;
	while (!q.empty()) {
		INFO cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			INFO next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			if (next.x < 0 || next.y < 0 || next.x >= 10 || next.y >= 6) {
				continue;
			}
			if (!visit[next.y][next.x] &&tmp[cur.y][cur.x] == tmp[next.y][next.x]) {				
				visit[next.y][next.x] = 1;
				q.push({ next.y,next.x });
			}
		}
		tmp[cur.y][cur.x] = 0; // remove
	}
	// re-copy
	for (int y = 0; y < 100; ++y) {
		for (int x = 0; x < 10; ++x) {
			map[y][x] = tmp[y][x];
		}
	}
}

// serach cells
void bfs(int sy, int sx) {
	visited[sy][sx] = 1;
	queue<INFO> q;
	q.push({ sy,sx });
	int cnt = 1;
	while (!q.empty()) {
		if (cnt >= k) {
			flag = false;
			boom(sy, sx);
			break;
		}
		INFO cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			INFO next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			if (next.x < 0 || next.y < 0 || next.x >= 10 || next.y >= 6) {
				continue;
			}
			if (!visited[next.y][next.x] && map[cur.y][cur.x] == map[next.y][next.x]) {
				visited[next.y][next.x] = 1;
				q.push({ next.y,next.x });
				cnt++;
			}
		}
	}
}

// gravity
void down(int sy, int sx) {
	while (true) {
		if (sy == n-1) break;
		if (map[sy + 1][sx] != 0) break;
		swap(map[sy][sx], map[sy + 1][sx]);
		sy = sy + 1;
	}
}

int main()
{
	scanf("%d %d", &n, &k);
	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < 10; ++x) {
			scanf("%1d", &map[y][x]);
		}
	}

	while (true) {
		flag = true;
		memset(visited, false, sizeof(visited));
		for (int y = 0; y < n; ++y) {
			for (int x = 0; x < 10; ++x) {
				if (map[y][x] != 0 && !visited[y][x]) {
					visited[y][x] = true;
					bfs(y,x);
				}
			}
		}
		if (flag) break;
		for (int y = n-2; y >= 0; --y) {
			for (int x = 0; x < 10; ++x) {
				if (map[y + 1][x] == 0) {
					down(y, x);
				}
			}
		}
	}

	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < 10; ++x) {
			printf("%d",map[y][x]);
		}
		printf("\n");
	}


	return 0;
}

90 6
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000200000
0000200000
0000300000
0000100000
0000100000
0000200000
0000202010
0200203030
3100202030
2300102120
1220132310
1130332120
3330232210
2230112323
2220322223
1110323221
2112221131
2111331233
3313322222
3323131331
2122132313
1321131333
3211213213
2333323213
3121123322
3112322113
1321123222
3122232121
2131332111
3323333211
3322211121
2121133323
1123333312
1233223311
2313113223
1313131312
2122122131
1312233111
1122123311
1313113133
2121333222
1333231131
2312112211
3332222122
2311212133
1311123133
1133231223
1311231323
1332313211
3231123123
1321211221
3333332232
2122113313
1211213221
1111122132
1111311231
1321113222
2333312331
1223331322
3132311212
1321313111
2232123122
3313332323
3223231121
2232131321
1222233223
3131222111
3133223113
2211112133
2233231313
3132313311
3312221221
2233122131
3323233131
2212113311
3222133323
1322332312

아래에..

코드 돌려보니 같은 숫자의 면적이 6이상이여도 사라지지 않는 경우가 있습니다.

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

문제

문제

출처

ICPC

예제는 잘 나오는데 틀렸다고 뜨네요ㅠㅠ

vire3064 4년 전 0

chw0501 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말