글 읽기 - 치즈문제 시간초과 부분 질문드립니다..

hys2rang 6년 전 0

시간초과 오류가 계속 뜨는데 어디부분을 수정해야할지 잘모르겠습니다...

#include <iostream>
#include <queue>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

vector <vector <bool>> visited;
vector <vector <int>> map;

int dx[4] = { 0,0,-1,1 };//위,아래,왼,오
int dy[4] = { -1,1,0,0 };

void isair(int a, int b);
int isvisited(int a, int b);

int main()
{
	int n, m;
	int sum = 0;
	int cnt = 0;
	int day = 0;

	cin >> n >> m;

	map.resize(101);
	visited.resize(101);
	for (int i = 0; i < 101; i++) {
		map[i].resize(101);
		visited[i].resize(101);
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		isair(n,m); //외부공기 = -1
        if(isvisited(n,m)==n*m){
            break;
        }
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if (map[i][j] != -1) {
					for (int k = 0; k < 4; k++) {
						if (map[i + dy[k]][j + dx[k]] < 0) {
							cnt++;
						}
					}
					if (cnt >= 2) {
						map[i][j] = 0;
					}
					cnt = 0;
				}
			}
		}
		day++;
	}
	cout << day-1 << endl;
	return 0;

}
void isair(int a,int b)
{
	queue <pair<int, int>> q;
	
	int x, y;
	int cnt = 0;

	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			if (map[i][j] == 0) {				
				for (int k = 0; k < 4; k++) {
					y = i + dy[k];
					x = j + dx[k];
					if (x >=0 && y>=0 && x<b && y <a && map[i + dy[k]][j + dx[k]] <0) {
						cnt++;
					}
				}
				if (cnt >= 2) {
					q.push({ j,i });
				}
				cnt = 0;
			}				
		}
	}

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;

		q.pop();

		if ((map[y][x] != 1)&& !visited[y][x]  ) { //  
			visited[y][x] = true;
			map[y][x] = -1;
			for (int i = 0; i < 4; i++) {
				int xx = x + dx[i];
				int yy = y + dy[i];
				if ((xx>=0 && yy>=0) && (xx<b && yy<a) && (!visited[yy][xx])) {
					q.push({ xx,yy });					
				}
			}
		}
	}

	return;
}

int isvisited(int a, int b)
{
	int cnt = 0;
	for (int k = 0; k < a; k++) {
		for (int l = 0; l < b; l++) {
			if (visited[k][l]) {
				cnt++;
			}
		}
	}
	return cnt;
}

djm03178 6년 전 0

외부공기 판별하는 부분이 이상합니다. 맨 바깥과 닿아있으면 외부공기여야 하는데, 그런 체크를 하는 부분이 보이지 않네요.

5 5

0 0 0 0 0

0 1 1 1 0

0 0 0 0 0

과 같은 케이스에서 무한루프가 걸립니다.

hys2rang 6년 전 0

감사합니다!! 다시한번 체크해볼께요!!!

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

문제

문제

출처

ICPC

치즈문제 시간초과 부분 질문드립니다..

hys2rang 6년 전 0

djm03178 6년 전 0

hys2rang 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말