## sicily 1048 Inverso 原

Ciel

### Description

The game of ‘Inverso’ is played on a 3x3 grid of colored fields (each field is either black or white). Each field is numbered as follows:
1  2  3
4  5  6
7  8  9
The player can click on a field, which will result in the inversion of that field and all its direct neighboring fields (i.e. the color changes from black to white or vice-versa). Hence,
Clicking field 1 inverts fields 1, 2, 4, 5
Clicking field 2 inverts fields 1, 2, 3, 4, 5, 6
Clicking field 3 inverts fields 2, 3, 5, 6
Clicking 4 inverts fields 1, 2, 4, 5, 7, 8
Clicking 5 inverts fields all fields
Clicking 6 inverts fields 2, 3, 5, 6, 8, 9
Clicking 7 inverts fields 4, 5, 7, 8
Clicking 8 inverts fields 4, 5, 6, 7, 8, 9
Clicking 9 inverts fields 5, 6, 8, 9
The aim of the game is to find the shortest sequence of clicks to make all fields white from a given start coloring of the grid.

### Input

The first line contains a number N (0≤N≤10000) of runs. The following N lines each contain a string of nine letters ‘b’ (black) or ‘w’ (white) for the color of the fields 1 to 9. This is the initial coloring of the grid.

### Output

For each input string the shortest word in the letters ‘1’… ‘9’ (for clicking field one, …, nine) which makes all fields white. If there is more than one shortest word then the lexicographically smallest one must be printed (‘1234’ is smaller than ‘1342’).

### Sample Input

``````3
bbwbwbwbw
bwwwbwbwb
bbbbwbbbw``````

### Sample Output

``````2459
267
356789``````

## 分析：

PS：此题天雷滚滚的地方是，答案必需是1-9的数字，也就是说输入是wwwwwwwww的时候，输出应该是11，卡了我很长时间才搞对。

## 代码：

``````// Problem#: 1048
// Submission#: 1853201
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

#define END 0

struct node{
int v;
string f;
node( int n ){
v = n;
f = "";
}
node( int n, string s ){
v = n;
f = s;
}
};

int field[10]={0,432,504,216,438,511,219,54,63,27};
bool visit[1<<9];

inline int toi( string s ){
int re = 0;
for( int i=0 ; i<9 ; i++ ){
re <<= 1;
re |= s[i]=='b' ? 1 : 0 ;
}
return re;
}

void bfs( int a ){
queue<node> buffer;
buffer.push(node(a));
visit[a] = true;
while( !buffer.empty() ){
node temp = buffer.front();
buffer.pop();
if( temp.v==END ){
cout << temp.f << endl;
return ;
}
for( int i=1 ; i<=9 ; i++ ){
int t = temp.v^field[i];
if( !visit[t] ){
visit[t] = true;
string s = temp.f;
s += '0'+i;
buffer.push(node(t,s));
}
}
}
}

int main(){
int n;
string str;
int start;
cin >> n;
while( n-- ){
cin >> str;
start = toi(str);
memset(visit,false,sizeof(visit));
if( start==0 ) cout << 11 << endl;
else bfs(start);
}
return 0;
}``````

### Ciel

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v\$database; 如果为noarchivelog模式，切换到archivelo......

UltraSQL
2018/07/23
0
0
for 和while 对cpu和内存的影响

snowyxueqian
2017/07/04
0
0

2016/07/08
440
3
sicily 1150 简单魔板 sicily 1151 魔板 sicily 1515 魔板C

Ciel
2012/12/15
949
1
sicily 1150,1151

2014/10/12
95
0

Java技术江湖

5
0

Moks角木

7
0
VUE 计算属性

6
0

Tomcat部署的基本概念 1. CATALINA_HOME与CATALINA_BASE分别指什么？ 　　　　CATALINA_HOME指的是Tomcat的安装目录 　　　　bin：\\Tomcat一些脚本存放目录，比如启动脚本startup.bat/start...

7
0
float浮动

float浮动 float浮动概念及原理： 文档流：文档流是文档中可显示对象在排列时所占用的位置。 加浮动的元素，会脱离文档流，会沿父容器靠左或靠右排列，如果之前已经有浮动的元素，会挨着浮动...

studywin

8
0