質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.48%

  • C++

    3617questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • プログラミング言語

    694questions

    プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

  • デバッグ

    99questions

    デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。

【競技プログラミング】全てのマス目を一度だけ通る単一の閉曲線

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 1,521

musharna000

score 12

AOJ 0236 Alien Messagesを解いていて詰まってしまったのでアドバイス頂きたいです。

0(通れる),1(通れない)でマップが与えられて、
そのマップに全ての0のマス目を一度だけ通る単一の閉曲線が描けるかどうかを判定する
という問題に対して、DFSで閉曲線がかけるかどうか判定するプログラムを書き、
ナイーブな実装だとTLEなので以下の条件で枝刈りをすることにしました。
(space_sumは0のマスの個数を表します)
・space_sumが4より少なかったらそもそも閉曲線がかけない
・space_sumが偶数でなければそもそも閉曲線がかけない
・DFSで今見ているマス(1にしてある)に隣接するマスおよびスタートのマスに隣接するマス以外で隣接するまだ見ていない(1にされていない)マスの個数が1のマスが存在したら突き当たりになるので閉曲線がかけない。

これで制限時間以内には通りましたが、WAになってしまいました。
そもそも上記の条件が間違っているのでしょうか、それとも実装にミスがあるのでしょうか。
コードを何度も確認してみたのですがどこが間違っているのか私にはわかりませんでした。
お判りの方おられましたら、コメント頂ければ幸いです。
宜しくお願い致します。
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <set>
#include <math.h>
#include <utility>
#include <stack>
#include <string.h>
#include <complex>
using namespace std;
const int INF = 1<<29;
const double EPS = 1e-8;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
struct edge{int to,cost;};

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};

int field[7][7];
int space_sum;
int W, H;
int sy, sx;

int get_dim(int y, int x){
    int dim = 0;
    for(int k=0;k<4;k++){
        int nx = x + dx[k], ny = y + dy[k];
        if(nx<0||W<=nx||ny<0||H<=ny)continue;
        if(field[ny][nx]==0) dim++;
    }
    return dim;
}

bool dfs(int y, int x, int d_sum){
    if(d_sum==space_sum){
        if(abs(sy-y)+abs(sx-x)==1)return true;
    }else{
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(field[i][j]) continue;
                if(abs(sy-i)+abs(sx-j)==1||abs(y-i)+abs(x-j)==1) continue;
                if(get_dim(i, j)==1) return false;
            }
        }
        for(int i=0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx<0||W<=nx||ny<0||H<=ny)continue;
            if(field[ny][nx]==0){
                field[ny][nx] = 1;
                if (dfs(ny, nx, d_sum+1)) return true;
                field[ny][nx] = 0;
            }
        }
    }
    return false;
}

int main(){
    while(cin >> W >> H, W){
        space_sum = 0;
        sy = -1; sx = -1;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                scanf("%d",&field[i][j]);
                space_sum += !field[i][j];
                if(sy<0&&!field[i][j]){
                    sy = i; sx = j;
                }
            }
        }
        field[sy][sx] = 1;
        if(space_sum<4||space_sum%2==1||!dfs(sy, sx, 1)){
            cout << "NO" << endl;
            continue;
        }else{
            cout << "YES" << endl;
        }
    }

    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+1

全てのマスに石像が配置されている場合にマズいことになりそうな気がします。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 14:17

    コメントありがとうございます。
    確かにfield[-1][-1]となるのでマズいですね。
    if(sy>=0) field[sy][sx] = 1;に修正してサブミットしてみたのですが、まだWAでした。
    もっと他の場所が間違っているみたいです。申し訳ありません。

    キャンセル

  • 2015/06/21 18:50

    sy == -1 のときに NO を返すようにはしてありますか?

    キャンセル

  • 2015/06/21 18:52

    sy == -1 のときは space_sum<4 の条件に引っかかるので NO になると思います。

    キャンセル

checkベストアンサー

0

大枠が間違っているようには思えませんでした。サンプルも通りますね。
W = H = 1 のときはどういう扱いでしょうか?閉曲線が書ける気がします。

だから、
  1.  1マスだけが空いている
  2.  2マスが連続して空いている
場合は特別扱いする必要があるかもしれませんね。

「入力データセットごとに、Yes または No を出力します。」
なので
YES や NO ではなく、Yes と No です。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 14:11

    コメントありがとうございます。
    1マスだけが空いているとき、2マスが連続して空いているときについて
    例外的にYESを出力するようにしてサブミットしてみましたがWAでした。
    上記のような場合は全ての0マスを一度だけ通る閉曲線とは言えないように思います。

    キャンセル

  • 2015/06/21 19:04

    致命的なミスを見つけましたので、追記しました。

    キャンセル

  • 2015/06/21 19:37

    >YES や NO ではなく、Yes と No です。
    ご指摘の通りでした。修正したところACされました。
    こんな初歩的なミスでお手を煩わせてしまって申し訳ないです。
    ご協力ありがとうございました!

    キャンセル

0

get_dimの引数のxとy,それとその中のif(field[ny][nx]==0)で使っているnxとnyがそれぞれ逆ではないでしょうか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/20 14:14

    0<=y座標<H, 0<=x座標<Wでget_dim(y座標, x座標)でfield[y座標][x座標]としてつかっているので大丈夫だと思います。get_dim内のnx,nyの書く順番が逆になっているので紛らわしかったですね。すみません。

    キャンセル

0

!0 は 1 なのでしょうか
ちょっと調べたところ 1, 非0 両方見受けられたので確証はないのですが、仮に 非0 だとすると
space_sum += !field[i][j];
の部分はマズい気がします。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/21 19:00

    気付かなかったですね…入力は 0/1 なので
    space_sum += (1 | field[i][j]);
    が良さそうでしょうか。

    キャンセル

  • 2015/06/21 19:02

    間違えました。XOR なので ^ ですね。

    キャンセル

  • 2015/06/21 19:39

    確かに環境によっては非0になるかもしれないのでこの書き方は良くないですね。
    気をつけようと思います。ご指摘ありがとうございました!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 受付中

    JavaScriptにおいて、GoogleMapsでの表示の仕方を変えたい!!

    はじめまして! 現在、一番下に記載したコードを用い、GoogleMapsにおいて以下のようなXMLファイルのデータを取り出してピンを表示させています。 また、PHPで受け取った緯度

  • 解決済

    template定数を使ったクラスのoperatorの定義方法

    template定数を用いて定義したクラスでoperatorを定義するにはどうしたらよいでしょうか。 使うクラスはX*Yのブロック(配列)の配列です。 //sample.cpp t

  • 受付中

    Unity、頂点の選択について

    1頂点を取得(選択)した後、その頂点の周りに接する頂点をまとめて選択するような方法を探しています。 また、いくつかの頂点を選択した後、一番端っこに属する頂点を選択から除くような処

  • 解決済

    c++のエラーについて

    前提・実現したいこと c++でデバッグ用の関数を作っているのですが,以下のようなエラーが出てしまい困っています. エラーメッセージ test.cpp:10:9: erro

  • 解決済

    配列の要素間の和を全パターン求めるプログラムを作成したい。

    皆様ありがとうございました。 前提・実現したいこと <CもしくはC++> 配列の要素間の和を全パターン求めるプログラムを作成したい。 【例】 /*-------------

  • 解決済

    std::vectorの添字がうまく機能しません

    前提・実現したいこと 現在C++とSiv3Dで落ち物パズルゲームを制作しています。 発生している問題・エラーメッセージ std::vectorを使用して'Block'クラスを格

  • 解決済

    同じ関数を2回呼び出すと動作が変わってしまう

    以下のような関数を作成します。 パラメータにはvectorを入れています。 template<typename Param> int kmp_match(const vecto

  • 受付中

    C++ 合計値 範囲指定

    C++で合計値を出力するプログラムを作成しています。プログラムを実行するとすべての和が出力されるのですが、 これを指定した範囲、例えば2、3、4、5の合計値を出力したい場合どうした

同じタグがついた質問を見る

  • C++

    3617questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • プログラミング言語

    694questions

    プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

  • デバッグ

    99questions

    デバッグはプログラムのバグや欠陥を検知し、開発中のバグを取り除く為のプロセスを指します。