BFS and think the problem reversely

Jimmy (xiaoke) Shen
2 min readNov 22, 2023

AtCoder ABC 329 E — Stamp

Last Saturday, there is a very nice problem from the AtCoder beginner contest.

The problem can be solved by using BFS if we think the problem reversely. This is not a very standard BFS and it is quit interesting.

Question

See here.

Basic idea

We think the problem reversely. Using t of “ABC” as example, to begin with if we find any ABC, then we can change it to “###” where the “#” means we can put anything as it will be covered by “ABC” later.

By doing this, we can first find all the ABC location and put it into a Queue, after that, we pop one, change it to all “###”, then we can find more qualified ones. For example:

1. ABCBABC
after replace the ABC to ###, we will have:
###B###
2. when pop the first "###", wen can check all possible overlap with this "###" one to find
next steps.
3. since #B# is valid choice as '#' can be put with anything, we can get
#######

After doing above, the last step will be check whether all the s’ characters can be replaced as ‘#’.

Solution in C++

#include<iostream>                                                                      
#include<queue>
#include<vector>
using namespace std;

void update(int i, int n, int m, string &s, string &t, queue<int>&Q, vector<int>& seen){
if (i < 0 || i + m > n || seen[i])return;
for (int j = 0; j < m ; ++j){
if (s[i + j] == '#' || s[i + j] == t[j])continue;
else return;
}
seen[i] = true;
Q.emplace(i);
return;
}
int main(){
int n, m;
string s, t;
cin>>n >> m >> s >> t;
vector<int> seen(n, 0);
queue<int> Q;
for (int i = 0; i < n; ++i){
update(i, n, m, s, t, Q, seen);
}
while(!Q.empty()){
auto i = Q.front();Q.pop();
for (int j = 0; j < m ; ++j){s[i + j ] = '#';
}
for (int j = -m + 1; j < m; ++j)
{
update(i + j, n, m, s, t, Q, seen);
}
}
if (s == string(n, '#'))cout << "Yes"<<endl;
else cout << "No" << endl;
return 0;
}

Thanks for reading.

--

--