随笔-141  评论-9  文章-3  trackbacks-0
状态转移方程:  dp[i][j] = dp[i][j] && dp[i+1][j] && dp[i][j+1] && dp[i+1][j+1]  , 时间复杂度O(n^3);

/*
ID: lorelei3
TASK: range
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int MAX = 255;

int n;
bool dp[MAX][MAX];

int main(){
    
int i,j,w;
    
char ch;
    ifstream fin(
"range.in");
    ofstream fout(
"range.out");

    fin
>>n;

    
for(i=0; i<n; ++i){
        
for(j=0; j<n; ++j){
            fin
>>ch;
            dp[i][j] 
= ch-'0';
        }

    }


    
for(w=2; w<=n; ++w){
        
int cnt = 0;
        
for(i=0; i<n; ++i)
            
for(j=0; j<n; ++j)
                
if(i+w<=&& j+w<=n){
                    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)
            fout
<<w<<" "<<cnt<<endl;
    }

    
return 0;
}


posted on 2011-01-13 22:34 小阮 阅读(149) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理