문제 URL : https://www.acmicpc.net/problem/20166
20166번: 문자열 지옥에 빠진 호석
K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.
www.acmicpc.net
문제 접근법 단순 bfs 혹은 dfs 문제입니다. 방문 처리가 필요없고 (1,1)->(1,2)->(1,1) 이런식으로 다시 돌아와도
새로운 문자열이 만들어 질수 있으니 이깊이가 최대 5를 넘어가지 않도록 해야합니다.
결국엔 최대 만들어질수 있는 문자열갯수가 2^8 * 10*10 이라 전체경우의수가 25600 정도이니 충분합니다.
소스코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
//By콩순이냉장고
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include<queue>
#include <unordered_map>
using namespace std;
int n, m, k;
int dy[] = { -1,-1,-1,0,0,1,1,1 };
int dx[] = { -1,0,1,-1,1,-1,0,1 };
char board[10][10];
unordered_map<string, int> set;
vector<string> v;
struct point {
int y, x, cnt;
string s;
};
void input() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
for (int i = 0; i < k; i++) {
string s;
cin >> s;
v.push_back(s);
set[s] = 0;
}
}
void bfs(int y, int x) {
string cur = "";
cur += board[y][x];
queue<point> q;
q.push({ y,x,1,cur });
while (!q.empty()) {
y = q.front().y;
x = q.front().x;
int cnt = q.front().cnt;
string s = q.front().s;
q.pop();
if (set.count(s))
set[s]++;
if (cnt >= 5)
continue;
for (int i = 0; i < 8; i++) {
int ny = (n + y + dy[i]) % n;
int nx = (m + x + dx[i]) % m;
q.push({ ny,nx,cnt + 1,s + board[ny][nx] });
}
}
}
void solve() {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
bfs(i, j);
}
}
for (int i = 0; i < k; i++)
cout << set[v[i]] << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
되도록 공감도 한표 부탁드립니당
'백준' 카테고리의 다른 글
| 백준 2997 네 번째 수 (0) | 2021.06.17 |
|---|---|
| 백준 11003 최솟값 찾기 (0) | 2021.05.27 |
| 백준 2539 모자이크 (0) | 2021.05.20 |
| 백준 3079 입국심사 (0) | 2021.05.20 |
| 백준 16434 드래곤 앤 던전 (0) | 2021.05.20 |