結果

問題 No.13 囲みたい！
コンテスト
ユーザー mizunomidori
提出日時 2016-07-01 23:46:22
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 2,515 bytes
コンパイル時間 756 ms
コンパイル使用メモリ 90,600 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 10:53:58
合計ジャッジ時間 1,259 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>

#define W_MAX 100
#define H_MAX 100

using namespace std;

class undirected_graph
{
    private:
        const int number_of_nodes;
        vector<int> *edges;
    public:
        undirected_graph(int n) : number_of_nodes(n) {edges = new vector<int>[number_of_nodes];}
        int size() {return number_of_nodes;}
        void make_edge(int x, int y)
        {
            edges[x].push_back(y);
            edges[y].push_back(x);
        }
        bool has_loop()
        {
            bool *used = new bool[number_of_nodes]();
            for (int i = 0; i < number_of_nodes; i++) {
                if (!used[i]) {
                    queue<pair<int, int> > q;
                    q.push(pair<int, int>(i, -1));
                    while (!q.empty()) {
                        int x, previous;
                        tie(x, previous) = q.front();
                        q.pop();
                        used[x] = true;
                        for (int j = 0; j < edges[x].size(); j++) {
                            int to = edges[x][j];
                            if (to == previous) {
                                continue;
                            } else if (used[to]) {
                                return true;
                            } else {
                                q.push(pair<int, int>(to, x));
                            }
                        }
                    }
                }
            }
            return false;
        }
};

int main(void)
{
    int W, H, M[W_MAX][H_MAX];
    cin >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> M[j][i];
        }
    }
    undirected_graph g(W * H);
    for (int i = 0; i < W - 1; i++) {
        for (int j = 0; j < H; j++) {
            if (M[i][j] == M[i + 1][j]) {
                g.make_edge(i*H + j, (i+1)*H + j);
            }
        }
    }
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H - 1; j++) {
            if (M[i][j] == M[i][j + 1]) {
                g.make_edge(i*H + j, i*H + (j+1));
            }
        }
    }
    if (g.has_loop()) {
        cout << "possible" << endl;
    } else {
        cout << "impossible" << endl;
    }
    return 0;
}
0