Sicily 1048: Inverso（BFS）

　　题意是给出一个3*3的黑白网格，每点击其中一格就会使某些格子的颜色发生转变，求达到目标状态网格的操作。可用BFS搜索解答，用vector储存每次的操作

 #include<bits/stdc++.h>

 using namespace std;

 struct Node{

     int num;//储存状态

     vector<int> path;//储存操作

 };

 int visit[];

 int click(int i, int num){

     int tmp = ;

     switch(i){

         case :tmp = num ^ ; break;//点击第0位，则0、1、3、4位取反，这里用异或实现，点击其他的同理

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

         case :tmp = num ^ ; break;

     }

     return tmp;

 }

 Node bfs(int n){

     queue<Node> q;

     Node front;

     front.num = n;

     q.push(front);

     while(!q.empty()){

         front = q.front(); q.pop();

         for(int i = ; i < ; i++){

             Node tmp = front;

             tmp.num = click(i, front.num);

             tmp.path.push_back(i+);

             if(tmp.num == ) return tmp;

             else{

                 if(!visit[tmp.num]){

                     q.push(tmp);

                     visit[tmp.num] = ;

                 }

             }

         }

     }

 }

 int main(){

     int n;

     cin >> n;

     while(n--){

         string s;

         cin >> s;

         int num = ;

         for(int i = ; i < s.size(); i++){

             if(s[i] == 'b')num = *num + ;

             else if(s[i] == 'w') num = *num;

         }

         memset(visit, , sizeof(visit));

         visit[num] = ;

         Node tmp = bfs(num);

         for(int i = ; i < tmp.path.size(); i++){

             cout << tmp.path[i];

         }

         cout << endl;

     }

 }