回答編集履歴

2

add

2018/07/13 14:50

投稿

papinianus
papinianus

スコア12705

test CHANGED
@@ -1,3 +1,229 @@
1
1
  List<T>を普通に比較したら、参照の比較になって同じインスタンスの参照でなければ、同値にはならないですね。
2
2
 
3
3
  ValueTupleにするか、クラス作ってIEquatable実装するか、!visited.Any(v=>v.SequenceEqual(next))みたいなラムダをかくかってとこですかね。
4
+
5
+
6
+
7
+ --解決したみたいなので蛇足
8
+
9
+ まず、visual studioを使ってください。C#はvisual studioがあってこそです。vsという解決策があるのに、エラーをコンパイルまで気付けないというのは大切な時間を無駄にしています(vs communityは個人の非商用とかを条件に無償で使えます)。
10
+
11
+
12
+
13
+ IEquatableはやろうとしていることに対して手間がかかりすぎる提案でした。
14
+
15
+ 提示いただいた入力例ではおそらくバグは発生せずに、abaみたいなものをyesにするのが問題だと理解しました。以前に書いていたラムダの件を反映したコードが↓
16
+
17
+ ```csharp
18
+
19
+ using System;
20
+
21
+ using System.Collections.Generic;
22
+
23
+ using System.Linq;
24
+
25
+ using System.Text;
26
+
27
+ using System.Threading.Tasks;
28
+
29
+ using System.Collections;
30
+
31
+ using static System.Console;
32
+
33
+
34
+
35
+ public class Program
36
+
37
+ {
38
+
39
+ public static int[] dx = { -1, 0, 1, 0 };
40
+
41
+ public static int[] dy = { 0, 1, 0, -1 };
42
+
43
+ public static int N;
44
+
45
+ public static char[][] map;
46
+
47
+ public static string str;
48
+
49
+
50
+
51
+ public static bool dfs(Stack<List<int>> visited, int y, int x, int count)
52
+
53
+ {
54
+
55
+ if (count == str.Length)
56
+
57
+ {
58
+
59
+ return true;
60
+
61
+ }
62
+
63
+ else
64
+
65
+ {
66
+
67
+ for (int i = 0; i < 4; i++)
68
+
69
+ {
70
+
71
+ int ny = y + dy[i];
72
+
73
+ int nx = x + dx[i];
74
+
75
+ List<int> next = new List<int> { ny, nx };
76
+
77
+ if (nx < 0 || nx >= N || ny < 0 || ny >= N)
78
+
79
+ {
80
+
81
+ continue;
82
+
83
+ }
84
+
85
+ else if (map[ny][nx] == str[count] && !visited.Any(v=>v.SequenceEqual(next)))
86
+
87
+ {
88
+
89
+ visited.Push(next);
90
+
91
+ count += 1;
92
+
93
+ if (dfs(visited, ny, nx, count))
94
+
95
+ {
96
+
97
+ return true;
98
+
99
+ }
100
+
101
+ else
102
+
103
+ {
104
+
105
+ count -= 1;
106
+
107
+ visited.Pop();
108
+
109
+ }
110
+
111
+ }
112
+
113
+ }
114
+
115
+ return false;
116
+
117
+ }
118
+
119
+ }
120
+
121
+ public static void Main()
122
+
123
+ {
124
+
125
+ // Your code here!
126
+
127
+ N = int.Parse(Console.ReadLine());
128
+
129
+ map = new char[N][];
130
+
131
+ for (int i = 0; i < N; i++)
132
+
133
+ {
134
+
135
+ map[i] = Console.ReadLine().ToCharArray();
136
+
137
+ }
138
+
139
+ int M = int.Parse(Console.ReadLine());
140
+
141
+ for (int i = 0; i < M; i++)
142
+
143
+ {
144
+
145
+ str = Console.ReadLine();
146
+
147
+ bool writable = false;
148
+
149
+ var visited = new Stack<List<int>>();
150
+
151
+ for (int j = 0; j < N; j++)
152
+
153
+ {
154
+
155
+ for (int k = 0; k < N; k++)
156
+
157
+ {
158
+
159
+ if (str[0] == map[j][k])
160
+
161
+ {
162
+
163
+ List<int> next = new List<int> { j, k };
164
+
165
+ visited.Push(next);
166
+
167
+ int count = 1;
168
+
169
+ if (dfs(visited, j, k, count))
170
+
171
+ {
172
+
173
+ System.Console.WriteLine("yes");
174
+
175
+ writable = true;
176
+
177
+ break;
178
+
179
+ }
180
+
181
+ else
182
+
183
+ {
184
+
185
+ count -= 1;
186
+
187
+ visited.Pop();
188
+
189
+ }
190
+
191
+ }
192
+
193
+ }
194
+
195
+ if (writable)
196
+
197
+ {
198
+
199
+ break;
200
+
201
+ }
202
+
203
+ }
204
+
205
+ if (!writable)
206
+
207
+ {
208
+
209
+ System.Console.WriteLine("no");
210
+
211
+ }
212
+
213
+ }
214
+
215
+ }
216
+
217
+ }
218
+
219
+ ```
220
+
221
+
222
+
223
+ ただ、こういう場合visitedをStack<List<int>>にするのではなく、stringにすればいいのではないかと思います(`next = j + "," + k;`のように)。そうすればvisited.Containsで判断してくれるはず。
224
+
225
+ もしくはもう少しOOPにするなら、`struct Positon { int x { get; set; } int y { get; set; } }`を定義しておいて、`next = new Positon() { x = j, y = k };`でもいいかもしれないです(visitedはStack<Position>型)。structは等値比較が暗黙に定義されるので。
226
+
227
+
228
+
229
+ 用途からすると文字列にするのがてっとりばやいと思います。(ちなみに string next = j + k;としてしまうと111が、1,11なのか11,1なのか識別できなくなるので、","みたいなjやkでは絶対に出てこない区切りを入れるといいかと思います)

1

修正

2018/07/13 14:50

投稿

papinianus
papinianus

スコア12705

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