'직사각형' 태그의 글 목록

'직사각형'에 해당되는 글 1건

2016.04.13 가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )

Coding/CPP 삽질기2016. 4. 13. 18:00

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )

/*
From :
http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem
*/

int findMaxRect (int rect[XSIZE][YSIZE]) {
	int ret = 0;
	unsigned int x = 0, y = 0, k = 0;
	int sum[YSIZE+1] = { 0, };
	int stack[YSIZE][2] = { 0, };
	int stIdx = -1;
	int width = 0;
	int y0 = 0, w0 = 0, tempArea = 0;
	
	for ( x = 0; x < XSIZE; ++x ) { 
		for ( y = 0; y <= YSIZE; ++y ) {
			sum[y] = rect[y][x] ? ++sum[y] : 0;
		}
		sum[YSIZE] = 0;
		width = 0;
		stIdx = -1;
		for ( y = 0; y <= YSIZE; ++y) {
			if ( sum[y] > width ) {
				stack[++stIdx][0] = y;
				stack[  stIdx][1] = width;
				width = sum[y];				
			} 
			else if ( sum[y] < width ) {

				while(1) {
					y0 = stack[stIdx  ][0];
					w0 = stack[stIdx--][1];
					tempArea =  width * (y - y0);
				  
					ret = tempArea > ret ? tempArea : ret;

					width = w0;
					if( sum[y] >= width) break;
				} 
				width = sum[y];
				if ( width != 0 ) {
					stack[++stIdx][0] = y0;
					stack[  stIdx][1] = w0;	
				}
			}
		}
	}	
	
	return ret;
}