質問編集履歴

1

ソースを全部載せました

2018/06/29 02:13

投稿

shinichi0326
shinichi0326

スコア47

test CHANGED
File without changes
test CHANGED
@@ -38,18 +38,170 @@
38
38
 
39
39
  ソースコード
40
40
 
41
+ import java.util.Scanner;
42
+
43
+ import java.util.Stack;
44
+
45
+
46
+
47
+ public class Main {
48
+
49
+ static final int[] dx = { -1, 0, 1, 0 };
50
+
51
+ static final int[] dy = { 0, 1, 0, -1 };
52
+
53
+ static int N;
54
+
55
+ static char[][] map;
56
+
57
+ static String string;
58
+
59
+
60
+
61
+ public static void main(String[] args) {
62
+
63
+ // 自分の得意な言語で
64
+
65
+ // Let's チャレンジ!!
66
+
67
+ Scanner sc = new Scanner(System.in);
68
+
69
+ N = sc.nextInt();
70
+
71
+ map = new char[N][];
72
+
73
+ for(int i=0; i<N; i++){
74
+
75
+ map[i]=sc.next().toCharArray();
76
+
77
+ }
78
+
79
+ int M = sc.nextInt();
80
+
81
+ for(int i=0; i<M; i++){
82
+
83
+ string = sc.next();
84
+
41
- int x = 1;
85
+ int x=0;
42
-
86
+
43
- int y = 2;
87
+ int y=0;
44
-
88
+
45
- List<Integer> next = new ArrayList<>();
89
+ Stack<int[]> visited = new Stack<>();
46
-
90
+
47
- next.add(y);
91
+ Boolean writable = false;
92
+
48
-
93
+ for(int j=0; j<N; j++){
94
+
95
+ for(int k=0; k<N; k++){
96
+
97
+ if(string.charAt(0)==map[j][k]){
98
+
99
+ y=j;
100
+
101
+ x=k;
102
+
49
- next.add(x);
103
+ int[] next = {y,x};
50
104
 
51
105
  visited.push(next);
52
106
 
107
+ int count=1;
108
+
109
+ if(dfs(visited,y,x,count)){
110
+
111
+ System.out.println("yes");
112
+
113
+ writable=true;
114
+
115
+ break;
116
+
117
+ }
118
+
119
+ }
120
+
121
+ }
122
+
123
+ if(writable){
124
+
125
+ break;
126
+
127
+ }
128
+
129
+ }
130
+
131
+ if(!writable){
132
+
133
+ System.out.println("no");
134
+
135
+ }
136
+
137
+ }
138
+
139
+ }
140
+
141
+
142
+
143
+ public static boolean dfs(Stack<int[]> visited, int sh, int sw, int count){
144
+
145
+ if(count==string.length()){
146
+
147
+ return true;
148
+
149
+ }else{
150
+
151
+ for (int i = 0; i < 4; i++) {
152
+
153
+ int nw = sw + dx[i];
154
+
155
+ int nh = sh + dy[i];
156
+
157
+ int[] next = {nh, nw};
158
+
159
+ if (nw < 0 || nw >= N || nh < 0 || nh >= N) {
160
+
161
+ continue;
162
+
163
+ }else if(map[nh][nw]==string.charAt(count) && !visited.contains(next)){
164
+
165
+ visited.push(next);
166
+
167
+ count+=1;
168
+
169
+ if(dfs(visited, nh, nw, count)){
170
+
171
+ return true;
172
+
173
+ }else{
174
+
175
+ count-=1;
176
+
177
+ visited.pop();
178
+
179
+ }
180
+
181
+ }
182
+
183
+ }
184
+
185
+ return false;
186
+
187
+ }
188
+
189
+ }
190
+
191
+ }
192
+
193
+
194
+
195
+
196
+
197
+
198
+
199
+
200
+
201
+
202
+
203
+
204
+
53
205
  ```
54
206
 
55
207