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

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. ABCBABCafter 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;                                                                           } `