結果

問題 No.157 2つの空洞
コンテスト
ユーザー lunnear
提出日時 2019-01-18 15:45:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,652 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 38,272 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-06 04:20:39
合計ジャッジ時間 991 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:78:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |     scanf("%d %d", &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <list>

class Vector2
{
public:
    Vector2(short x = 0, short y = 0):x(x), y(y){}
    short x, y;
    
    float LengthSq(){return (x * x + y * y);}
    
    Vector2 operator -(Vector2 &a){return Vector2(x - a.x, y - a.y);}
};

struct Square
{
    char val = -1;
    bool check = false;
};

class Field
{
public:
    Field(int w, int h);
    ~Field();
    
private:
    int w, h;
    Square *sq;
    
public:
    Square* Get(int x, int y);
    bool isField(int x, int y);
};



Field::Field(int w, int h)
{
    this->w = w;
    this->h = h;
    
    sq = new Square[w * h];
}

Field::~Field()
{
    delete[] sq;
}

Square* Field::Get(int x, int y)
{
    return &sq[x + y * w];
}

bool Field::isField(int x, int y)
{
    if(x < 0)
        return false;
    
    if(y < 0)
        return false;
    
    if(x >= w)
        return false;
    
    if(y >= h)
        return false;
    
    return true;
}


int main()
{
    int w, h;
    scanf("%d %d", &w, &h);
    getchar();

    Field f(w, h);
    
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            
            Square *s = f.Get(x, y);
            
            s->val = (getchar() == '#')? 0:1;
        }
        getchar();
    }
    
    std::list<Vector2> holl[2];
    
    int count = 0;
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            
            Square *s = f.Get(x, y);
            
            if(s->check)
                continue;
            
            if(s->val != 1)
                continue;
            
            std::list<Vector2> history;
            while(1)
            {
                s->check = true;
                
                bool next = false;
                const Vector2 d[4] = {
                    {-1, 0},
                    { 1, 0},
                    { 0, -1},
                    { 0,  1}
                };
                for(int i = 0; i < 4; i++)
                {
                    if(!f.isField(x + d[i].x, y + d[i].y))
                        continue;
                    
                    Square *to = f.Get(x + d[i].x, y + d[i].y);
                    
                    if(to->val && !to->check)
                    {
                        Vector2 v;
                        v.x = x; v.y = y;
                        history.push_back(v);
                        s = to;
                        x += d[i].x; y += d[i].y;
                        next = true;
                        break;
                    }
                }
                if(next)
                    continue;
                
                holl[count].push_back(Vector2(x, y));
                
                if(history.empty())
                    break;
                

                Vector2 v = history.back();
                s = f.Get(v.x, v.y);
                x = v.x; y = v.y;
                history.pop_back();
            }
            
            count++;
            if(count == 2)
                break;
        }
        if(count == 2)
            break;
    }
    
    
    Vector2 *v0, *v1;
    int min = 999;
    for(auto i = holl[0].begin(); i != holl[0].end(); i++)
    {
        for(auto j = holl[1].begin(); j != holl[1].end(); j++)
        {
            Vector2 v = (*i) - (*j);
            int l = abs(v.x) + abs(v.y);
            
            if(l < min)
            {
                v0 = &(*i);
                v1 = &(*j);
                min = l;
                
                if(min == 2)
                    break;
            }
        }
    }
    
    min -= 1;

    printf("%d\n", min);
    return 0;
}
0