阿里4.1笔试第一题解法

• 阿里4.1笔试第一题思路：
  • 从串s开始bfs搜索,看是否能搜到全0
  • 中间用map<string, int>记录搜索过的串，避免重复

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e6+5;
const double inf = 1e12;

/*

3
01
011
00110

*/

map<string, int> mp;
queue<string> q;

int main(){
    int t;
    scanf("%d", &t);
    string s;
    while(t--){
        cin>>s;
        mp.clear();
        mp[s] = 0;
        q.push(s);
        int n = s.size();
        while(!q.empty()){
            string u = q.front();
            q.pop();
            for(int i=0; i<n; i++){
                string tmp = u;
                tmp[i] = tmp[i] == '0' ? '1' : '0';
                if(i + 1 < n){
                    tmp[i+1] = tmp[i+1] == '0' ? '1' : '0';
                }
                if(i - 1 >= 0){
                    tmp[i-1] = tmp[i-1] == '0' ? '1' : '0';
                }
                if(mp.count(tmp) == 0){
                    mp[tmp] = mp[u] + 1;
                    q.push(tmp);
                }
            }
        }
        string zero = "";
        for(int i=0; i<s.size(); i++) zero += '0';
        if(mp.count(zero) == 0){
            printf("NO\n");
        }
        else{
            printf("%d\n", mp[zero]);
        }
    } 
    return 0;
}