文档章节

sicily 1048 Inverso

Ciel
 Ciel
发布于 2013/01/03 19:49
字数 663
阅读 82
收藏 0

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

分析:

本题主要考察广度搜索方法的应用。首先,注意到本题是操作次数(即生成图的边)最重要,其次才是顶点顺序,那么就要采用以边为搜索线索的广度搜索,而非深搜,深搜会WA。

另外,本题最好采用二进制表示棋盘状态,操作简便而且节省运行时间,代码也更简洁,而9种操作对应的是当前状态数和特定数字的异或。另外,状态矩阵是必需的,不然可能会超时。

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

代码:

// Problem#: 1048
// Submission#: 1853201
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// 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;
}

© 著作权归作者所有

下一篇: sicily 1034 Forest
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

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

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

关于while 和for循环的cpu性能以及内存占用情况 同样的脚本文件,分别使用for和while完成,再用top查看cpu和内存的情况。 [root@localhostfish]# cat sumwhile.sh #!/bin/bash # declare-i ...

snowyxueqian
2017/07/04
0
0
为什么两个mysql同时监听3306?

之前本机安装了mysql5.5,端口是3306,后来要弄php,就装了个php的集成环境wampserver,这个自带mysql5.6.12,因为我的mysql5.5一直是运行着的,看网上,人家安装wampserver都会报错,wampser...

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

这三道题目大体相同,只是数据处理方式不同,需要修改的地方很少,因此只以1150为例说明即可。 Description 魔板由8个大小相同方块组成,分别用涂上不同颜色,用1到8的数字表示。 其初始状态...

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

// Problem#: 1151// Submission#: 2982372// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License// URI: http://creativecom......

猜猜我是吧
2014/10/12
95
0

没有更多内容

加载失败,请刷新页面

加载更多

从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0
VUE 计算属性

本文转载于:专业的前端网站▶VUE 计算属性 1、示例代码 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <title>vue示例</title> </hea......

前端老手
昨天
6
0
快速搭建LNMT平台和环境部署 Tomcat详解

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

网络小虾米
昨天
7
0
float浮动

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

studywin
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部