# BFS and think the problem reversely

**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.