[アルゴリズム解析]BOJ 5547信号ランプ

今日から、アルゴリズムを解くことを続けたいと思います.
下半期の终わりが近づいているとき.気持ちは悪いが、上半期の準備をやり直すなら、コートを通過する実力を気兼ねなく作らなければならない.
今日の質問はBOJ 5547アルミニウム合金です.グラフィック探求問題銀色第一段階の問題です確かに久しぶりなので時間がかかりました

BOJ 5547アルミニウム合金

裕福な家庭の後継者である尚勤の4軒の家は図のように1メートルの正六角形に貼られている.もうすぐクリスマスなので、彼女を喜ばせるために、尚根は建物の壁を明かりで飾るつもりだ.見えないところに照明を飾るのはもったいないと思ったので、外に見えるところだけを飾りたい.

上図は上空から見た上根四軒の建物のレイアウトです.正六角形の数字は座標を表します.ここでは、灰色の正六角形が建物の位置で、白は建物のない場所です.上に赤い線で表記されている部分は外から見える壁で、この壁に照明を飾ります.壁の長さは64メートルです.
もし上根があなたの家の建築位置地図をあげたら、プログラムを書いて、装飾照明の壁面の長さの和を求めてください.地図の外は自由に行き来できる場所で、隣の建物の間は通れません.

にゅうしゅつりょく

[入力]
1行目は2つの整数WとHを与える.(1≦W,H≦100)次のH行には4つの上根の家屋が配置されている.i+1行では、W個の整数がスペースで区切られている.j第(1≦j≦w)整数の座標は(j,i)、建物がある場合は1、建物がない場合は0である.与えられた入力には少なくとも1つの建物があります.
地図は以下のルールで作られています.

地図の左上隅の正六角形の座標は(1,1)です.

(x,y)右族の正六角形の座標は(x+1,y)である.

yが奇数である場合、下方の正六角形の座標は(x,y+1)である.

yが偶数の場合、右下角正六角形の座標は(x,y+1)である.

[出力]
装飾照明の壁面長の和を出力します.

私の答え

座標の六角変化を実現

最も悩ましい問題は,六角形をどのように二次元配列に表すかである.特定の位置で6方向に伸び、4方向に隣接する形で表現するという考えは思いつかない.
これは簡単な問題で、私は考えが難しいと思います.座標値の変化を確認すればよい.六角形の位置をつかみ、右上から時計回りに座標がどのように変化しているかをチェックし、座標の変化を配列に記録することができます.
しかし、デバッグ中に座標値が一致しないことがわかり、何度チェックしても原因が分かりません.そして線の位置が奇数なのか偶数なのかで座標の変化量が違います!
六角形は一列に並ぶのではなく、当たり前のこと…!

外壁の区別-内壁

六角形位置から座標変化量を区切って解き,誤った答え値を得た.同様に,デバッグにより原因を知る過程で,内壁と外壁を区別しなければならないことを認識し,探索を行う.
ここでは少し工夫を凝らして結論的に与えられた配列よりも,上り,列値2を加えて配列寸法を決めるので,(0,0)からBFS探索に達し,0値の格子を全て2に置き換えて外壁を表すことができる.入力した建物は(1,1)の後に入力しなければならず、(0,0)からナビゲートしても問題ありません.

正解を見つける

どちらも解決すれば、正しい答えが出やすい.
事件に記録されている1価の格子を基準にBFSの探索を行い,隣接する格子の外壁格子に遭遇するとedgeの価格を上げ,最終正解に加算することができる.内壁は建物内とみなされ、1->2でカウントする必要があります.
久しぶりに解けた、比較的簡単な質問でも、結構時間がかかったようです.
もう一度始めよう!!

コード#コード#

#include <iostream>
#include <vector>
#include <queue>

// boj 5547 일루미네이션 실버1, bfs
using namespace std;

// 짝수 행일 때 
int even_dy[6] = {-1,0,1,1,0,-1};
int even_dx[6] = {0,1,0,-1,-1,-1};

// 홀수 행일 때 
int odd_dy[6] = {-1,0,1,1,0,-1};
int odd_dx[6] = {1,1,1,0,-1,0};

int R, C;

// 테두리 계산하기 
int bfs(vector<vector<int>> map, vector<vector<bool>> & visited,int row, int col){
    int edge = 0;

    queue<pair<int, int>> point;
    point.push({row, col});
    visited[row][col] = true;

    while (!point.empty()){
        pair<int,int> cur = point.front();
        point.pop();

        for (int i = 0; i < 6; ++i) {
            int move_row, move_col;

            if (cur.first % 2 == 0){
                move_row = even_dy[i];
                move_col = even_dx[i];
            }else{
                move_row = odd_dy[i];
                move_col = odd_dx[i];
            }

            int nr = cur.first + move_row;
            int nc = cur.second + move_col;

            if (nr<0 || nr>R+1 || nc<0 || nc>C+1) continue;

            if (map[nr][nc]== 2) edge++;
            else{
                if (!visited[nr][nc]){
                    visited[nr][nc] = true;
                    point.push({nr,nc});
                }
            }

        }
    }

    return edge;
}

// 외벽 구분하기 
void makeOutsideWall(vector<vector<int>> & map, int R, int C){
    vector<vector<bool>> visited(R+2, vector<bool>(C+2, false));
    queue<pair<int,int>> point;

    point.push({0,0});  //(0,0) 외벽에서 인접한 외벽 탐색 시작 
    visited[0][0] = true;

    while (!point.empty()){
        pair<int, int> loc = point.front();
        map[loc.first][loc.second] = 2;
        point.pop();

        int move_r, move_c;
        for (int k = 0; k < 6; ++k) {
            if (loc.first%2==0) {
                move_r = even_dy[k];
                move_c = even_dx[k];
            }else{
                move_r = odd_dy[k];
                move_c = odd_dx[k];
            }

            int nr = loc.first+move_r;
            int nc = loc.second+move_c;

            if(nr<0||nr>R+1||nc<0||nc>C+1) continue;
            if (map[nr][nc]==0 && !visited[nr][nc]){
                visited[nr][nc] = true;
                point.push({nr,nc});
            }
        }
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>C>>R;

    vector<vector<int>> map(R+2, vector<int>(C+2,0));
    vector<vector<bool>> visited(R+2, vector<bool>(C+2, false));

    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) cin>>map[i][j];
    }

    makeOutsideWall(map, R, C);


    int answer = 0;
    for (int i = 0; i <= R+1 ; ++i) {
        for (int j = 0; j <= C+1 ; ++j) {
            if (!visited[i][j] && map[i][j]== 1){
                answer += bfs(map, visited, i, j);
            }
        }
    }

    cout<<answer;

   return 0;
}

Reference

[白俊]5547号:イルミネーション