dp題。用dp[i][j][m]表示左上角為(i,j)，邊長(zhǎng)為m的正方形是否完整。那么
如果dp[i][j][m]完整，則當(dāng)且僅當(dāng)dp[i][j][m-1],dp[i+1][j][m-1],dp[i][j+1][m-1],dp[i+1][j+1][m-1]的正方形也是完整的(畫個(gè)圖就很清晰了)。由于我們從上到下，從左到右掃描每個(gè)點(diǎn)，在每一輪i,j用過(guò)一次，就不會(huì)再使用，所以只需用二維數(shù)組保存dp[i][j]，即可。
時(shí)間復(fù)雜度為O(n^3),空間復(fù)雜度為O(n^2)。analysis中有個(gè)時(shí)間復(fù)雜度為O(n^2),空間O(n)的解法。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?fin("range.in");
ofstream?fout("range.out");
#ifdef?_DEBUG
#define?out?cout
#define?in?cin
#else
#define?out?fout
#define?in?fin
#endif
bool?dp[250][250];
int?side_len;
void?input()
{
????in>>side_len;
????char?t;
????for(int?i=0;i<side_len;++i){
????????for(int?j=0;j<side_len;++j){
????????????while(?in.get(t)&&isspace(t)?);
????????????dp[i][j]?=?t-'0';
????????}
????}
}
void?solve()
{
????input();
????for(int?w?=?2;w<=side_len;++w){
????????int?cnt?=?0;
????????for(int?i=0;i<side_len;++i){
????????????for(int?j=0;j<side_len;++j){
????????????????if(i+w<=side_len&&j+w<=side_len){
????????????????????dp[i][j]?=?dp[i][j]&&dp[i+1][j]&&dp[i][j+1]&&dp[i+1][j+1];
????????????????????if(dp[i][j])
????????????????????????cnt++;
????????????????}
????????????}
????????}
????????if(cnt!=0){
????????????out<<w<<"?"<<cnt<<endl;
????????}
????}
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}