Largest Allowed Area

時間限制:?1 Sec??內存限制:?128 MB
提交:?146??解決:?54
[提交] [狀態] [命題人:admin]

題目描述

A company is looking for land to build its headquarters. It has a lot of money and can buy as many land patches as it needs. Its goal, however, is finding the largest square region containing no forest. Unfortunately, there is no such region that is large enough for the headquarters they want to build.?
? ?
After negotiation with the government and the evaluation of environmental impacts, the government allows the company to purchase land with at most one forest patch. In other words, the company’s goal is now finding the largest square region containing at most one forest patch.?
?
To facilitate the search process, the company creates a map in the form of a 2D table consisting R rows and C columns. In this 2D table, each entry represents a land of patch where 0 corresponds to a non-forest patch and 1 to a forest patch. Unfortunately, the map may have up to 1,000 x 1,000 entries and it is not a good idea to manually look for the largest allowed square region. This is where your skill comes into play. Write an efficient algorithm to find such a square region.?

?

輸入

The first line is a positive integer T <= 20 representing the number of test cases. For each case, the input is formatted as follows.?

Note: there is at least one non-forest patch in each test case.?

?

輸出

There are T lines in the output. Each line is the number of rows in the largest allowed square region for each case.?

?

樣例輸入

復制樣例數據

2 
10 20 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1  
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20 10 
1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0

樣例輸出

9
7

題目大意：

先輸入一個整數t，代表有t組測試樣例，對于每組測試樣例，先輸入兩個整數n,m，然后輸入n行m列的0,1矩陣，問在這個0,1矩陣中選取一個正方形區域，使得這個正方形區域內有且僅有一個1，問這樣的正方形邊長最大是多少。

解題思路：

可以通過二分正方形的邊長，對于每次二分的mid，可以先預處理一下0,1矩陣，用sum[i][j]代表第i行第j列的元素的左上角的全部元素和，因此根據容斥思想可得出推導公式sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]，若一個正方形區域內僅包含一個1，則證明這個正方形區域的面積為1，因此對于每次二分出的正方形的邊長，可以通過遍歷一下這個矩陣，判斷此邊長是否會是的某個正方形區域的面積為1.

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int arr[1200][1200];
int sum[1200][1200];
int n,m;
bool judge(int x) {rep(i,1,n-x) {rep(j,1,m-x) {int t=sum[i+x][j+x]-sum[i+x][j-1]-sum[i-1][j+x]+sum[i-1][j-1];if(t==1) return true;}}return false;
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;scanf("%d",&t);while(t--) {scanf("%d %d",&n,&m);rep(i,1,n) {rep(j,1,m) {arr[i][j]=sum[i][j]=0;scanf("%d",&arr[i][j]);sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];}}int l=1,r=min(n,m);while(r-l>1) {int mid=(r+l)>>1;if(judge(mid)) l=mid;else r=mid;}printf("%d\n",l+1);}return 0;
}

?