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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

Q&A

解決済

2回答

1911閲覧

C# Stack に 要素数2個の整数 List を Push し Contains で含まれるか確かめる

shinichi0326

総合スコア47

C#

C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

0グッド

0クリップ

投稿2018/07/12 10:15

前提・実現したいこと

ここに質問の内容を詳しく書いてください。
C#でスタックに要素数2の整数リストをプッシュしContainsで要素が含まれているかどうか
判別する時、既に含まれているリストを含まれていると判別してしまう

発生している問題・エラーメッセージ

スタックにリストをプッシュする時Containsでうまく判別できない

### 該当のソースコード using System; using System.Collections; using System.Collections.Generic; using System.Linq; using static System.Console; public class Hello{ public static int[] dx = {-1,0,1,0}; public static int[] dy = {0,1,0,-1}; public static int N; public static char[][] map; public static string str; public static bool dfs(Stack visited, int y, int x, int count){ if(count==str.Length){ return true; }else{ for(int i=0; i<4; i++){ int ny = y + dy[i]; int nx = x + dx[i]; List<int> next = new List<int>{ny, nx}; if(nx<0 || nx>=N || ny<0 || ny>=N){ continue; }else if(map[ny][nx]==str[count] && !visited.Contains(next)){ visited.Push(next); count+=1; if(dfs(visited, ny, nx, count)){ return true; }else{ count-=1; visited.Pop(); } } } return false; } } public static void Main(){ // Your code here! N = int.Parse(Console.ReadLine()); map = new char[N][]; for(int i=0; i<N; i++){ map[i]=Console.ReadLine().ToCharArray(); } int M = int.Parse(Console.ReadLine()); for(int i=0; i<M; i++){ str=Console.ReadLine(); bool writable = false; var visited = new Stack(); for(int j=0; j<N; j++){ for(int k=0; k<N; k++){ if(str[0]==map[j][k]){ List<int> next = new List<int>{j, k}; visited.Push(next); int count=1; if(dfs(visited,j,k,count)){ System.Console.WriteLine("yes"); writable=true; break; }else{ count-=1; visited.Pop(); } } } if(writable){ break; } } if(!writable){ System.Console.WriteLine("no"); } } } } ```ここに言語名を入力 C# ソースコード

試したこと

Visual Studio でデバッグした所 !visited.Contains(next) の部分で
visitedに含まれているnextが条件を通過してしまう

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

papinianus

2018/07/12 10:53 編集

入力サンプルはご提示いただけない感じですか?←回答に関係ないので忘れてください
shinichi0326

2018/07/12 10:53

4 abcd efgh hgfe dcba 5 abfgf bfgc abfga hdc fghde
guest

回答2

0

細かいところまで見ておりませんが、

  • visited.Contains(next) は visitedに nextという List<int>インスタンスが含まれいるかを判定しているのであって、リストの中身がどうであるかを判定してるわけではないです。
  • nextはループの中なかで毎回newしたオブジェクトなのですから、visited.Contains(next) の結果はつねに false だと思います。

投稿2018/07/12 10:53

編集2018/07/12 22:44
ebiryo

総合スコア797

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

shinichi0326

2018/07/13 00:41

回答ありがとうございます。 的確に問題点を指摘して頂き大変勉強になりました。 本来ならベストアンサーにしたいのですが、papinianusさんが 具体的な解決方法を提示してくれましたので 今回はpapinianusさんをベストアンサーにさせて頂きます。
guest

0

ベストアンサー

List<T>を普通に比較したら、参照の比較になって同じインスタンスの参照でなければ、同値にはならないですね。
ValueTupleにするか、クラス作ってIEquatable実装するか、!visited.Any(v=>v.SequenceEqual(next))みたいなラムダをかくかってとこですかね。

--解決したみたいなので蛇足
まず、visual studioを使ってください。C#はvisual studioがあってこそです。vsという解決策があるのに、エラーをコンパイルまで気付けないというのは大切な時間を無駄にしています(vs communityは個人の非商用とかを条件に無償で使えます)。

IEquatableはやろうとしていることに対して手間がかかりすぎる提案でした。
提示いただいた入力例ではおそらくバグは発生せずに、abaみたいなものをyesにするのが問題だと理解しました。以前に書いていたラムダの件を反映したコードが↓

csharp

1using System; 2using System.Collections.Generic; 3using System.Linq; 4using System.Text; 5using System.Threading.Tasks; 6using System.Collections; 7using static System.Console; 8 9public class Program 10{ 11 public static int[] dx = { -1, 0, 1, 0 }; 12 public static int[] dy = { 0, 1, 0, -1 }; 13 public static int N; 14 public static char[][] map; 15 public static string str; 16 17 public static bool dfs(Stack<List<int>> visited, int y, int x, int count) 18 { 19 if (count == str.Length) 20 { 21 return true; 22 } 23 else 24 { 25 for (int i = 0; i < 4; i++) 26 { 27 int ny = y + dy[i]; 28 int nx = x + dx[i]; 29 List<int> next = new List<int> { ny, nx }; 30 if (nx < 0 || nx >= N || ny < 0 || ny >= N) 31 { 32 continue; 33 } 34 else if (map[ny][nx] == str[count] && !visited.Any(v=>v.SequenceEqual(next))) 35 { 36 visited.Push(next); 37 count += 1; 38 if (dfs(visited, ny, nx, count)) 39 { 40 return true; 41 } 42 else 43 { 44 count -= 1; 45 visited.Pop(); 46 } 47 } 48 } 49 return false; 50 } 51 } 52 public static void Main() 53 { 54 // Your code here! 55 N = int.Parse(Console.ReadLine()); 56 map = new char[N][]; 57 for (int i = 0; i < N; i++) 58 { 59 map[i] = Console.ReadLine().ToCharArray(); 60 } 61 int M = int.Parse(Console.ReadLine()); 62 for (int i = 0; i < M; i++) 63 { 64 str = Console.ReadLine(); 65 bool writable = false; 66 var visited = new Stack<List<int>>(); 67 for (int j = 0; j < N; j++) 68 { 69 for (int k = 0; k < N; k++) 70 { 71 if (str[0] == map[j][k]) 72 { 73 List<int> next = new List<int> { j, k }; 74 visited.Push(next); 75 int count = 1; 76 if (dfs(visited, j, k, count)) 77 { 78 System.Console.WriteLine("yes"); 79 writable = true; 80 break; 81 } 82 else 83 { 84 count -= 1; 85 visited.Pop(); 86 } 87 } 88 } 89 if (writable) 90 { 91 break; 92 } 93 } 94 if (!writable) 95 { 96 System.Console.WriteLine("no"); 97 } 98 } 99 } 100}

ただ、こういう場合visitedをStack<List<int>>にするのではなく、stringにすればいいのではないかと思います(next = j + "," + k;のように)。そうすればvisited.Containsで判断してくれるはず。
もしくはもう少しOOPにするなら、struct Positon { int x { get; set; } int y { get; set; } }を定義しておいて、next = new Positon() { x = j, y = k };でもいいかもしれないです(visitedはStack<Position>型)。structは等値比較が暗黙に定義されるので。

用途からすると文字列にするのがてっとりばやいと思います。(ちなみに string next = j + k;としてしまうと111が、1,11なのか11,1なのか識別できなくなるので、","みたいなjやkでは絶対に出てこない区切りを入れるといいかと思います)

投稿2018/07/12 10:52

編集2018/07/13 14:50
papinianus

総合スコア12705

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

shinichi0326

2018/07/12 22:54

普段はpython3を書いておりC#は勉強がてら書いています。 なのでIEquatableといっても知識がありません。 ネットで調べて見ていろいろ書いてみましたが上手くいきません。 ちょっとしたサンプルを書いて頂けないでしょうか? 無理言ってすいません。
papinianus

2018/07/13 00:08 編集

分からなかったらその後どうしようもないとおもうのですが、ラムダではダメなのでしょうか?このラムダは動くはず。 ここで長いコードかくのつらいのでgistとかでもいいですか?書けるとして、今晩以降になります。
shinichi0326

2018/07/13 00:37

誠に勝手を言って申し訳ありませんでした。 ネットでIEquatableを再度検索した所 上手くいきました。 しかし、上手くいった理由がよくわかりません。 手続き型言語はインタプリタと違ってコンパイル通すだけでも 一苦労なので苦手です。 勉強不足を痛感しました。 また、何かわからないことがありましたら、ご教授ください。
papinianus

2018/07/13 14:51

追記しましたが、visual studioを使ってください。エラーがその場で分かります。入力アシストもあります(intellisense)。コンパイル通すだけで一苦労というのはあなたの大切な時間を無駄にしています。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問