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

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

新規登録して質問してみよう
ただいま回答率
86.02%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

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

Q&A

解決済

競技プログラミング JOI 薄氷渡り WAの原因

djrjd
djrjd

総合スコア1

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

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

1回答

0グッド

0クリップ

481閲覧

投稿2022/11/29 08:56

編集2022/11/29 10:04

JOIの薄氷渡りという問題を正解することができません。
https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d
このコードをどのように書き換えれば
正答を得ることができますか?

C++

1#include <bits/stdc++.h> 2 3using namespace std; 4using Node = vector<vector<int>>; 5vector<int> dxs ={1,0,-1,0}; 6vector<int> dys ={0,1,0,-1}; 7 int n,m; 8int ans = 0; 9// 深さ優先探索 10vector<bool> seen; 11void dfs(int x,int y,int v,vector<vector<int>> &G) { 12 G[x][y] = 0; 13 v++; 14 15ans = max(v,ans); 16 17 for(int i = 0; i < 4; i++){ 18 int x2 = x + dxs[i]; 19 int y2 = y + dys[i]; 20 if((0 <= x2 && x2 < x) && (0 <= y2 && y2 < y)){ 21 if(G[x2][y2] == 1){ 22 dfs(x2,y2,v,G); 23 } 24 } 25 } 26G[x][y] = 1; 27} 28 29int main() { 30 31 cin >> n >> m; 32 33 vector<vector<int>> G(n,vector<int>(m)); 34 35 36 for(int i = 0; i < n; i++){ 37for(int j = 0; j < m; j++){ 38 cin >> G[i][j]; 39 40} 41 } 42 for(int i = 0; i < n; i++){ 43for(int j = 0; j < m; j++){ 44 if(G[i][j]==1){ 45 46 dfs(i,j,0,G); 47} 48} 49 } 50 cout << ans; 51} 52

以下のような質問にはグッドを送りましょう

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

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

気になる質問をクリップする

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

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

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

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

適切な質問に修正を依頼しましょう。

djrjd

2022/11/29 09:20 編集

このコードで、正答できない原因を教えていただきたいです。 質問を書かず、すいませんでした。
Zuishin

2022/11/29 09:24

解説と正答例を見てもわからないということですか?
djrjd

2022/11/29 09:51 編集

正答例を見てみると理解できるのですが、それを模写したこのコードではすべての入力に対して1が出力されてしまい、自分では原因が分からず質問をしました。 重ねてお詫び申し上げます。

回答1

1

ベストアンサー

c++

1//20行目 2if((0 <= x2 && x2 < x) && (0 <= y2 && y2 < y)){

この条件だと、探索中のマスの左上のマスしか条件に入っていません。探索候補である上下左右のマスが除外されてしまっているため、探索が打ち切りになってしまい、1が出力されます。

マス(x2, y2)が広場からはみ出ていないかを確かめるif文ですから、x, yではなく、右端と下端を表すn, mで挟みます。

c++

1if((0 <= x2 && x2 < n) && (0 <= y2 && y2 < m)){

後は、出力の末尾に改行を入れればACできると思います。

c++

1cout << ans << endl;

投稿2022/11/29 12:27

編集2022/11/29 15:01
luuguas

総合スコア459

djrjd👏を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

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

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

このような回答には修正を依頼しましょう。

回答へのコメント

djrjd

2022/11/29 14:25

ありがとうございました。 無事解決することができました。

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

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

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