結果

問題 No.697 池の数はいくつか
ユーザー lunnear
提出日時 2019-01-12 06:12:28
言語 C++11（廃止可能性あり）
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 524 ms / 6,000 ms
コード長 2,934 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 310 ms
コンパイル使用メモリ 35,840 KB
実行使用メモリ 20,480 KB
最終ジャッジ日時 2024-11-08 08:08:26
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:71:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

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

struct Vector2
{
    short x, 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(void)
{
    int w, h;
    scanf("%d %d", &h, &w);
    getchar();

    Field f(w, h);
    
    int zeros = 0;
    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            
            Square *s = f.Get(x, y);
            
            s->val = getchar() - '0';


            if(s->val == 0)
                zeros++;
            
            getchar();
        }
    }
    
    int *min = (w < h)? &w:&h;
    if(*min > zeros)
    {
        printf("1\n");
        return 0;
    }
    
    
    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;
                
                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++;
        }
    }
    
    printf("%d\n", count);
    return 0;
}
0