[UVa] 10074 - Take the Land

題目網址: http://goo.gl/lasekr

題 意: 給定一張由 0、1 表示而成的 m * n 二維地圖， 0 代表空地， 1 代表樹木，且每格面積單位為 1 ，問地圖上最大的矩形空地面積為多少( 1 <= m, n <= 100 )。


解法: 將地圖上，0改成1，1改成 -100000，題目就變成從地圖上找出總和最大的矩形，就是常見的二維連續和問題，用DP解，複雜度 O(M^2*N)，在此就不詳述了。

TAG: DP

注意:

程式碼:

	/**
	* Tittle: 10074 - Take the Land
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/16
	* File: 10074 - Take the Land.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	#define INF -100000
	// declarations
	int m, n;
	int mat[N][N];
	// functions
	int maxSum1d( int arr[], int l )
	{
	static int ret, sum;
	sum = ret = 0;
	FOR( i, 1, l ) {
	if( sum+arr[i] < 0 ) sum = 0;
	else sum += arr[i];
	ret = max( ret, sum );
	}
	return ret;
	}
	int maxSum2d( int arr[][N], int row, int col )
	{
	static int ret, sum, tmp[N];
	ret = 0;
	FOR( k, 1, row ) {
	clr( tmp, 0 );
	FOR( i, k, row ) {
	FOR( j, 1, col ) tmp[j] += arr[i][j];
	ret = max( ret, maxSum1d( tmp, col ) );
	}
	}
	return ret;
	}
	// main function
	int main( void )
	{
	int val;
	// input
	while( scanf( "%d%d", &m, &n )==2 && (m||n) ) {
	FOR( i, 1, m ) FOR( j, 1, n ) {
	scanf( "%d", &val );
	if( val ) mat[i][j] = INF;
	else mat[i][j] = 1;
	}
	// solve & output
	printf( "%d\n", maxSum2d( mat, m, n ) );
	}
	return 0;
	}

view raw 10074 - Take the Land.cpp hosted with ❤ by GitHub