グリッドグラフ
(graph/grid-graph.hpp)

• View this file on GitHub
• Last update: 2021-08-01 23:46:19+09:00
• Include: #include "graph/grid-graph.hpp"
• Link: https://atcoder.jp/contests/abc020/submissions/18517344

Depends on

• graph/template.hpp

Code

#ifndef __GRAPH__GRID__GRAPH
#define __GRAPH__GRID__GRAPH
/**
 * @brief グリッドグラフ
 * 使用例: https://atcoder.jp/contests/abc020/submissions/18517344
 * 
 */
#include "template.hpp"
#include <cassert>
#include <string>
#include <vector>

namespace grid_graph {
using grid_t = std::vector<std::string>;
int H, W;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int xy2id(int x, int y) { return y*W+x; }
int id2x(int id) { return id%W; }
int id2y(int id) { return id/W; }
bool outside(int x, int y) {
    if (x < 0 || x >= W) return true;
    if (y < 0 || y >= H) return true;
    return false;
}

int cost(char c) {
    // FIXME: ここを実装する
    int inf = 1<<30;
    if (c == '#') return inf;
    return 1;
}

Graph<int> build(const grid_t& grid) {
    Graph<int> ret(H*W);
    assert(grid.size() == H);
    assert(grid[0].size() == W);
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            int id = xy2id(x,y);
            for (int d = 0; d < 4; ++d) {
                int nx = x+dx[d];
                int ny = y+dy[d];
                if (outside(nx,ny)) continue;
                int nid = xy2id(nx,ny);
                int c = cost(grid[ny][nx]);
                ret[id].emplace_back(id, nid, c);
            }
        }
    }
    return ret;
}

int find_pos(const grid_t& grid, char c) {
    // cが初めに見つかった位置を返す
    // 見つからなければ-1
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            if (grid[y][x] == c) {
                return xy2id(x,y);
            }
        }
    }
    return -1;
}
} // namespace grid_graph

#endif // __GRAPH__GRID__GRAPH

#line 1 "graph/grid-graph.hpp"


/**
 * @brief グリッドグラフ
 * 使用例: https://atcoder.jp/contests/abc020/submissions/18517344
 * 
 */
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 9 "graph/grid-graph.hpp"
#include <cassert>
#include <string>
#line 12 "graph/grid-graph.hpp"

namespace grid_graph {
using grid_t = std::vector<std::string>;
int H, W;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int xy2id(int x, int y) { return y*W+x; }
int id2x(int id) { return id%W; }
int id2y(int id) { return id/W; }
bool outside(int x, int y) {
    if (x < 0 || x >= W) return true;
    if (y < 0 || y >= H) return true;
    return false;
}

int cost(char c) {
    // FIXME: ここを実装する
    int inf = 1<<30;
    if (c == '#') return inf;
    return 1;
}

Graph<int> build(const grid_t& grid) {
    Graph<int> ret(H*W);
    assert(grid.size() == H);
    assert(grid[0].size() == W);
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            int id = xy2id(x,y);
            for (int d = 0; d < 4; ++d) {
                int nx = x+dx[d];
                int ny = y+dy[d];
                if (outside(nx,ny)) continue;
                int nid = xy2id(nx,ny);
                int c = cost(grid[ny][nx]);
                ret[id].emplace_back(id, nid, c);
            }
        }
    }
    return ret;
}

int find_pos(const grid_t& grid, char c) {
    // cが初めに見つかった位置を返す
    // 見つからなければ-1
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            if (grid[y][x] == c) {
                return xy2id(x,y);
            }
        }
    }
    return -1;
}
} // namespace grid_graph

Back to top page