[导入]zoj1002

 

#include <vector>
#include <iostream>
using namespace std;
int length,ops;
vector<vector<int> > city;
int openCount(int x,int y)
{
    int co=0;
    if(x>0&&city[x-1][y]!=0)co++;
    if(y>0&&city[x][y-1]!=0)co++;
    if(x<length-1&&city[x+1][y]!=0)co++;
    if(y<length-1&&city[x][y+1]!=0)co++;
    return co;
}
void setFlag(int x,int y)
{
    for(int s=x-1;s>=0;s--)
    {
        if(city[s][y]==0)break;
        else if(city[s][y]!=-2) {city[s][y]=-2;ops--;}
    }
    for(int s=y-1;s>=0;s--)
    {
        if(city[x][s]==0)break;
        else if(city[x][s]!=-2) {city[x][s]=-2;ops--;}
    }
    for(int s=x+1;s<length;s++)
    {
        if(city[s][y]==0)break;
        else if(city[s][y]!=-2) {city[s][y]=-2;ops--;}
    }
    for(int s=y+1;s<length;s++)
    {
        if(city[x][s]==0)break;
        else if(city[x][s]!=-2) {city[x][s]=-2;ops--;}
    }
}
int getFlag(int x,int y)
{
    int co=0;
    for(int s=x-1;s>=0;s--)
    {
        if(city[s][y]==0)break;
        else co++;
    }
    for(int s=y-1;s>=0;s--)
    {
        if(city[x][s]==0)break;
        else co++;
    }
    for(int s=x+1;s<length;s++)
    {
        if(city[s][y]==0)break;
        else co++;
    }
    for(int s=y+1;s<length;s++)
    {
        if(city[x][s]==0)break;
        else co++;
    }
    return co;
}
int main()
{
    while(cin>>length&&length!=0)
    {
    char c;
    ops=0;
    if(length==1)
    {
        cin>>c;
        if(c=='.')cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
    else
    {
        city.clear();
        city.resize(length,vector<int>(length));
        int count=0;
        int min_open,min_fl;
        int opc=0,flag=0;
        int x,y;
        for(int i=0;i<length;i++)
            for(int j=0;j<length;j++)
            {
                cin>>c;
                if(c=='.'){city[i][j]=1;ops++;}
                else city[i][j]=0;
            }
        while(ops!=0)
        {
            min_open=5;
            min_fl=16;
            for(int i=0;i<length;i++)
                for(int j=0;j<length;j++)
                {
                    if(city[i][j]==1)
                    {
                        opc=openCount(i,j);
                        flag=getFlag(i,j);
                        if((opc<min_open)||(opc==min_open&&flag<min_fl))
                        {min_fl=flag;min_open=opc;x=i;y=j;}
                    }
                }
            city[x][y]=-1;
            ops--;
            count++;
            setFlag(x,y);
        }
        cout<<count<<endl;
    }
    }
    return 0;
}

 虽然终于AC过去了,但其实还是失败的,因为我都不能证明自己的算法是正确的...大学时学得真是忘得差不多了,要好好补补算法的基础知识了~~下次写个心中有数的算法再AC一次!

I'm back! 

作者: Barryhe 发表于 2011-10-21 15:15 原文链接

评论: 0 查看评论 发表评论


最新新闻:
· 调研称超1/3年轻人视网络如空气:离开无法生存(2011-11-04 14:09)
· 社交旅游网站Gogobot融资1500万美元,打造旅游爱好者的全能助手(2011-11-04 13:54)
· Digg创始人Kevin Rose新项目Oink上线,让你为周围的任何东西打分(2011-11-04 13:53)
· Dark Sky:无温度,无湿度,无风力的天气预报(2011-11-04 13:39)
· “摇一摇,味道更好”——雅虎发布“鸡尾酒”Web开发技术(2011-11-04 13:36)

编辑推荐:你正在成长为一名优秀的程序员吗?

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库


文章来源:http://www.cnblogs.com/heqile/archive/2011/10/21/2220322.html

posted on 2011-10-21 15:15 Barryhe 阅读(116) 评论(0)  编辑 收藏 引用


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


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜