BOJ 23085 - 판치기
이 작으므로 BFS로 풀어줄 수 있다.
현재 상태를 가 몇개가 있는지로 두자.
현재 개수에서 를 개 뒤집기로 했다면, 는 개 뒤집는다.
그럼 결국 가 개 생기고 가 개 생기므로 는 개 생긴다.
이렇게 BFS로 최단경로를 돌려주면 된다.
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
int h = cntt(s, 'H');
vi vis(n + 1);
queue<int> q;
q.push(h);
vis[h] = 1;
int ans = 0;
while (sz(q)) {
int size = sz(q);
while (size--) {
int cur = q.front();
if (cur == 0) goto out;
q.pop();
for (int h = 0; h <= k; h++) {
int t = k - h;
int nxt = cur - h + t;
if (cur >= h && n - cur >= t && !vis[nxt]) {
vis[nxt] = 1;
q.push(nxt);
}
}
}
ans++;
}
out:;
cout << (!vis[0] ? -1 : ans);
}
Comments