結果

問題 No.697 池の数はいくつか
ユーザー lunnear
提出日時 2019-01-12 06:12:28
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 530 ms
コード長 2,934 Byte
コンパイル時間 150 ms
使用メモリ 18,768 KB
最終ジャッジ日時 2019-04-28 12:01:56

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1_sample1.txt AC 2 ms
6,872 KB
1_sample2.txt AC 3 ms
6,872 KB
1_sample3.txt AC 2 ms
6,868 KB
2_case1.txt AC 2 ms
6,868 KB
5_gen_case1.txt AC 2 ms
6,872 KB
5_gen_case2.txt AC 3 ms
6,872 KB
5_gen_case3.txt AC 2 ms
8,916 KB
5_gen_case4.txt AC 2 ms
6,872 KB
5_gen_case5.txt AC 3 ms
6,868 KB
5_gen_case6.txt AC 2 ms
6,868 KB
5_gen_case7.txt AC 2 ms
6,872 KB
5_gen_case8.txt AC 1 ms
6,868 KB
5_gen_case9.txt AC 3 ms
6,868 KB
5_gen_case10.txt AC 3 ms
6,872 KB
5_gen_case11.txt AC 2 ms
6,872 KB
5_gen_case12.txt AC 3 ms
8,916 KB
5_gen_case13.txt AC 2 ms
6,872 KB
5_gen_case14.txt AC 1 ms
6,872 KB
5_gen_case15.txt AC 3 ms
6,868 KB
5_gen_case16.txt AC 2 ms
6,868 KB
5_gen_case17.txt AC 2 ms
8,912 KB
5_gen_case18.txt AC 3 ms
6,872 KB
5_gen_case19.txt AC 2 ms
8,920 KB
5_gen_case20.txt AC 2 ms
6,868 KB
9_gen_case1.txt AC 63 ms
6,868 KB
9_gen_case2.txt AC 62 ms
6,872 KB
9_gen_case3.txt AC 64 ms
8,912 KB
9_gen_case4.txt AC 63 ms
6,872 KB
9_gen_case5.txt AC 63 ms
8,912 KB
10_gen_case.txt AC 140 ms
18,768 KB
11_gen_case.txt AC 530 ms
18,764 KB
テストケース一括ダウンロード

ソースコード

diff #
#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