ABC302-B 解説
B - Find snuke
$H \times W$ のグリッドからsnukeを探す問題です。
解法1
向きに対して全部書く方法です。
H, W = map(int, input().split()) S = [input() for _ in range(H)] for i in range(H): for j in range(W - 4): if S[i][j] == 's' and S[i][j + 1] == 'n' and S[i][j + 2] == 'u' and S[i][j + 3] == 'k' and S[i][j + 4] == 'e': print(i + 1, j + 1) print(i + 1, j + 2) print(i + 1, j + 3) print(i + 1, j + 4) print(i + 1, j + 5) if S[i][j + 4] == 's' and S[i][j + 3] == 'n' and S[i][j + 2] == 'u' and S[i][j + 1] == 'k' and S[i][j] == 'e': print(i + 1, j + 5) print(i + 1, j + 4) print(i + 1, j + 3) print(i + 1, j + 2) print(i + 1, j + 1) for i in range(H - 4): for j in range(W): if S[i][j] == 's' and S[i + 1][j] == 'n' and S[i + 2][j] == 'u' and S[i + 3][j] == 'k' and S[i + 4][j] == 'e': print(i + 1, j + 1) print(i + 2, j + 1) print(i + 3, j + 1) print(i + 4, j + 1) print(i + 5, j + 1) if S[i + 4][j] == 's' and S[i + 3][j] == 'n' and S[i + 2][j] == 'u' and S[i + 1][j] == 'k' and S[i][j] == 'e': print(i + 5, j + 1) print(i + 4, j + 1) print(i + 3, j + 1) print(i + 2, j + 1) print(i + 1, j + 1) for i in range(H - 4): for j in range(W - 4): if S[i][j] == 's' and S[i + 1][j + 1] == 'n' and S[i + 2][j + 2] == 'u' and S[i + 3][j + 3] == 'k' and S[i + 4][j + 4] == 'e': print(i + 1, j + 1) print(i + 2, j + 2) print(i + 3, j + 3) print(i + 4, j + 4) print(i + 5, j + 5) if S[i + 4][j + 4] == 's' and S[i + 3][j + 3] == 'n' and S[i + 2][j + 2] == 'u' and S[i + 1][j + 1] == 'k' and S[i][j] == 'e': print(i + 5, j + 5) print(i + 4, j + 4) print(i + 3, j + 3) print(i + 2, j + 2) print(i + 1, j + 1) if S[i + 4][j] == 's' and S[i + 3][j + 1] == 'n' and S[i + 2][j + 2] == 'u' and S[i + 1][j + 3] == 'k' and S[i][j + 4] == 'e': print(i + 5, j + 1) print(i + 4, j + 2) print(i + 3, j + 3) print(i + 2, j + 4) print(i + 1, j + 5) if S[i][j + 4] == 's' and S[i + 1][j + 3] == 'n' and S[i + 2][j + 2] == 'u' and S[i + 3][j + 1] == 'k' and S[i + 4][j] == 'e': print(i + 1, j + 5) print(i + 2, j + 4) print(i + 3, j + 3) print(i + 4, j + 2) print(i + 5, j + 1)
#include <bits/stdc++.h> using namespace std; int main() { int H, W; cin >> H >> W; vector<string> S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } for (int i = 0; i < H; i++) { for (int j = 0; j < W - 4; j++) { if (S[i][j] == 's' && S[i][j + 1] == 'n' && S[i][j + 2] == 'u' && S[i][j + 3] == 'k' && S[i][j + 4] == 'e') { cout << i + 1 << ' ' << j + 1 << '\n'; cout << i + 1 << ' ' << j + 2 << '\n'; cout << i + 1 << ' ' << j + 3 << '\n'; cout << i + 1 << ' ' << j + 4 << '\n'; cout << i + 1 << ' ' << j + 5 << '\n'; } if (S[i][j + 4] == 's' && S[i][j + 3] == 'n' && S[i][j + 2] == 'u' && S[i][j + 1] == 'k' && S[i][j] == 'e') { cout << i + 1 << ' ' << j + 5 << '\n'; cout << i + 1 << ' ' << j + 4 << '\n'; cout << i + 1 << ' ' << j + 3 << '\n'; cout << i + 1 << ' ' << j + 2 << '\n'; cout << i + 1 << ' ' << j + 1 << '\n'; } } } for (int i = 0; i < H - 4; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == 's' && S[i + 1][j] == 'n' && S[i + 2][j] == 'u' && S[i + 3][j] == 'k' && S[i + 4][j] == 'e') { cout << i + 1 << ' ' << j + 1 << '\n'; cout << i + 2 << ' ' << j + 1 << '\n'; cout << i + 3 << ' ' << j + 1 << '\n'; cout << i + 4 << ' ' << j + 1 << '\n'; cout << i + 5 << ' ' << j + 1 << '\n'; } if (S[i + 4][j] == 's' && S[i + 3][j] == 'n' && S[i + 2][j] == 'u' && S[i + 1][j] == 'k' && S[i][j] == 'e') { cout << i + 5 << ' ' << j + 1 << '\n'; cout << i + 4 << ' ' << j + 1 << '\n'; cout << i + 3 << ' ' << j + 1 << '\n'; cout << i + 2 << ' ' << j + 1 << '\n'; cout << i + 1 << ' ' << j + 1 << '\n'; } } } for (int i = 0; i < H - 4; i++) { for (int j = 0; j < W - 4; j++) { if (S[i][j] == 's' && S[i + 1][j + 1] == 'n' && S[i + 2][j + 2] == 'u' && S[i + 3][j + 3] == 'k' && S[i + 4][j + 4] == 'e') { cout << i + 1 << ' ' << j + 1 << '\n'; cout << i + 2 << ' ' << j + 2 << '\n'; cout << i + 3 << ' ' << j + 3 << '\n'; cout << i + 4 << ' ' << j + 4 << '\n'; cout << i + 5 << ' ' << j + 5 << '\n'; } if (S[i + 4][j + 4] == 's' && S[i + 3][j + 3] == 'n' && S[i + 2][j + 2] == 'u' && S[i + 1][j + 1] == 'k' && S[i][j] == 'e') { cout << i + 5 << ' ' << j + 5 << '\n'; cout << i + 4 << ' ' << j + 4 << '\n'; cout << i + 3 << ' ' << j + 3 << '\n'; cout << i + 2 << ' ' << j + 2 << '\n'; cout << i + 1 << ' ' << j + 1 << '\n'; } if (S[i + 4][j] == 's' && S[i + 3][j + 1] == 'n' && S[i + 2][j + 2] == 'u' && S[i + 1][j + 3] == 'k' && S[i][j + 4] == 'e') { cout << i + 5 << ' ' << j + 1 << '\n'; cout << i + 4 << ' ' << j + 2 << '\n'; cout << i + 3 << ' ' << j + 3 << '\n'; cout << i + 2 << ' ' << j + 4 << '\n'; cout << i + 1 << ' ' << j + 5 << '\n'; } if (S[i][j + 4] == 's' && S[i + 1][j + 3] == 'n' && S[i + 2][j + 2] == 'u' && S[i + 3][j + 1] == 'k' && S[i + 4][j] == 'e') { cout << i + 1 << ' ' << j + 5 << '\n'; cout << i + 2 << ' ' << j + 4 << '\n'; cout << i + 3 << ' ' << j + 3 << '\n'; cout << i + 4 << ' ' << j + 2 << '\n'; cout << i + 5 << ' ' << j + 1 << '\n'; } } } }
解法2
向きを簡単に全探索する方法です。縦、横、斜めに一直線上に連続して等間隔に並んでいるということは、横のindexと縦のindexの差は $-1,0,1$ のいずれかです。 これはforループで簡単に書くことができます。どちらも0のパターンに注意しましょう。
H, W = map(int, input().split()) S = [input() for _ in range(H)] s = "snuke" for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: if dx == 0 and dy == 0: continue for x in range(H): for y in range(W): if 0 <= x + 4 * dx < H and 0 <= y + 4 * dy < W: if all(S[x + i * dx][y + i * dy] == s[i] for i in range(5)): for i in range(5): print(x + i * dx + 1, y + i * dy + 1)
#include <bits/stdc++.h> using namespace std; int main() { int H, W; cin >> H >> W; vector<string> S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } string s = "snuke"; for (int dx: {-1, 0, 1}) { for (int dy: {-1, 0, 1}) { if (dx == 0 && dy == 0) { continue; } for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { if (0 <= x + 4 * dx && x + 4 * dx < H && 0 <= y + 4 * dy && y + 4 * dy < W) { bool ok = true; for (int i = 0; i < 5; i++) { if (S[x + i * dx][y + i * dy] != s[i]) { ok = false; } } if (ok) { for (int i = 0; i < 5; i++) { cout << x + i * dx + 1 << ' ' << y + i * dy + 1 << '\n'; } } } } } } } }
解法3
始点を全探索する方法です。解法2とあまり変わりませんが、forの順番を交換して、さらに始点は必ずsなので、そうでない無駄なケースを省くことができて解法2より高速です。
H, W = map(int, input().split()) S = [input() for _ in range(H)] s = "snuke" for x in range(H): for y in range(W): if S[x][y] != 's': continue for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: if (dx != 0 or dy != 0) and 0 <= x + 4 * dx < H and 0 <= y + 4 * dy < W: if all(S[x + i * dx][y + i * dy] == s[i] for i in range(1, 5)): for i in range(5): print(x + i * dx + 1, y + i * dy + 1)
#include <bits/stdc++.h> using namespace std; int main() { int H, W; cin >> H >> W; vector<string> S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } string s = "snuke"; for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { if (S[x][y] != 's') { continue; } for (int dx: {-1, 0, 1}) { for (int dy: {-1, 0, 1}) { if ((dx != 0 || dy != 0) && 0 <= x + 4 * dx && x + 4 * dx < H && 0 <= y + 4 * dy && y + 4 * dy < W) { bool ok = true; for (int i = 1; i < 5; i++) { if (S[x + i * dx][y + i * dy] != s[i]) { ok = false; } } if (ok) { for (int i = 0; i < 5; i++) { cout << x + i * dx + 1 << ' ' << y + i * dy + 1 << '\n'; } } } } } } } }
