[白俊]15684号はしご操作

質問リンク:https://www.acmicpc.net/problem/15684

質問する

はしご遊びは、N本の縦線とM本の横線で構成されています.隣接する縦線の間に横線を配置することができ、各縦線に横線を配置できる位置の個数はHであり、すべての縦線は同じ位置を有する.下図はN=5,H=6の場合の図で横線はありません.

緑の線は縦線を表し、緑の線と破線が交差する点は横線を置くことができる点である.横線は隣接する2本の縦線を接続しなければならない.ただし、2本の横線は連続または接続できません.また、横線は破線上にあるはずです.

上の図には全部で5本の横線がある.横線は、上の図のように隣接する2本の縦線に接続し、横線を配置できる位置に接続します.
梯子ゲームは縦線ごとにゲームを行い、縦線の一番上から下の方向に行きます.この場合、横線に遭遇した場合は、横線を使用してサイド縦線に移動し、移動した縦線から下に移動します.
上の図では1番が3番、2番が2番、3番が5番、4番が1番、5番が4番で到着しています.次の2枚の図は1番と2番がどのように移動したのかです.

はしごに横線を付けて、はしごゲームの結果を操作しようとします.この場合、i番縦線の結果はi番になるはずです.そのためには、横線数の最大値を求めるプログラムを作成します.

入力

第1行目では、縦線の個数N、横線の個数Mが与えられ、各縦線が横線の位置を置くことができる個数Hが与えられる.(2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H)
2行目から、M行では1行に横線の情報が与えられます.
横線の情報は2つの整数aとbで表される.(1≦a≦H,1≦b≦N−1)b番縦線とb+1番縦線がa番破線位置で接続されていることを意味する.
一番上の破線番号は1番で、下に行くたびに1が増えます.縦線の一番左の番号は1番で、右に着くたびに1が増えます.
入力された横線が互いに連続する場合はありません.

しゅつりょく

はしごゲームを操作して、i番縦線の結果がi番になるようにすると、追加する横線の個数の最大値が出力されます.答えが3より大きい場合は、-1が出力されます.また、不可能な場合でも−1を出力する.

問題を理解する

はしご操作で出発はしごと到着はしごを同じにします.置くことができる梯子数は3つで、最小梯子数を求める問題です.
これはdfsの問題です.はしごがつながってはいけない.

質問へのアクセス

入力

梯子を修正します.

梯子を順番に置きます.(dfs)

梯子を取り付けることができる場合は、出発梯子と到着梯子が同じであることを確認してください.

4番が本当なら、終わりでなければ2-4回繰り返します.

コード実装（C++）

#include <iostream>
#include <vector>

using namespace std;

int minLadder = -1;
int ladder;
int X, Y;
int map[31][11] = {0, };

bool check(){
    for(int i = 1 ; i <= X ; i++){
        int nx = i;
        for(int j = 1 ; j <= Y ; j++){
            if(map[j][nx] == 1) nx = nx + 1;
            else if(nx-1 >= 1 && map[j][nx-1]) nx = nx - 1;
        }
        if(nx != i) return false;
    }
    return true;
}

void dfs(int y, int cnt){
    if(minLadder != -1) return;
    if(cnt == ladder){
        if(check()) minLadder = cnt;
        return;
    }
    else{
        for(int ny = y; ny <= Y ; ny++){
            for(int nx = 1 ; nx < X ; nx++){
                if(map[ny][nx+1] || map[ny][nx-1] || map[ny][nx]) continue;
                map[ny][nx] = 1;
                dfs(ny, cnt+1);
                map[ny][nx] = 0;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int ladderNum;
    cin >> X >> ladderNum >> Y;
    int tempX, tempY;
    for(int i = 0 ; i < ladderNum ; i++){
        cin >> tempY >> tempX;
        map[tempY][tempX] = 1;
    }

    for(int i = 0 ; i <= 3 ; i++){
        ladder = i;
        dfs(1,0);
        if(minLadder != -1) break;
    }
    cout << minLadder << "\n";
}