Bailian2813 画家问题【暴力】

Stella981
• 阅读 655

2813:画家问题
总时间限制: 1000ms 内存限制: 65536kB
描述
有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。
Bailian2813 画家问题【暴力】

输入
第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15
来源
1681

问题链接Bailian2813 画家问题
问题简述:(略)
问题分析:这个问题与参考链接可以说是同一个问题,只是输入输出不同。解题代码是使用那个代码修改而来,同样采用暴力法实现。

数据表示方面,使用数组press[][]来存储开关按下标记。需要扩充1行即下标为0的行,需要扩充2列即下标为0的列和下标为7的列。press[i][j]=1表示第i行第j列需要按下,press[i][j]=0表示第i行第j列不需要按下。
采用逐行枚举的方法来实现。对第一行进行枚举,枚举所有的可能(000000-111111),开始时先看第一行为000000(都不按按钮)的情况,然后采用逐步加1的方式来实现。
首先需要关掉第i行的灯,可以通过按第i+1行来实现。一般而言,若b[i][j]灯亮,则需要按b[i+1][j]。这样,可以采用从第2行开始,逐行递推进行暴力枚举方法来解决。
另外,press[i][j]值由初始灯的状态,和前面行按按钮的情况算出。
程序说明:(略)
参考链接Bailian2811 熄灯问题【暴力】
题记:(略)

AC的C++语言程序如下:

/* Bailian2813 画家问题 */

#include <bits/stdc++.h>

using namespace std;

const int N = 15;
char g[N + 1][N + 2];
int b[N + 1][N + 2], press[N + 1][N + 2];
int ans;

void solve(int n)
{
    for(int i = 2 ; i <= n; i++) {
        for(int j = 1 ; j <= n; j++) {
            press[i][j] = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2;

        }
    }

    /* 检查最后一行是否都已经关灯 */
    bool flag = true;
    for(int j = 1 , i = n + 1; j <= n ; j++) {
        int t = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2;
        if(t) {flag = false; break;}
    }

    if(flag) {
        int cnt = 0;
        for(int i = 1 ; i <= n; i++)
            for(int j = 1 ; j <= n; j++)
                if(press[i][j]) cnt++;
        ans = min(ans, cnt);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    for(int i = 1; i <= n; i++)
        scanf("%s", g[i] + 1);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(g[i][j] == 'w') b[i][j] = 1;
            else if(g[i][j] == 'y') b[i][j] = 0;


    memset(press, 0, sizeof(press));
    ans = n * n + 1;
    for(;;) {
        solve(n);

        /* 对于第1行进行枚举,000000-111111,采用加1方式实现 */
        int t = 1;
        press[1][t]++;
        while(press[1][t] > 1) {
            press[1][t] = 0;
            t++;
            press[1][t]++;
        }
        if(t > n) break;
    }

    if(ans == n * n + 1)
        printf("inf\n");
    else
        printf("%d\n", ans);

    return 0;
}

/*
5
wwwww
wwwww
wwwww
wwwww
wwwww
5
ywyyy
wwwyy
ywyyy
yyyyy
yyyyy
5
ywyyy
wwyyy
yywwy
yywyy
yyyyy

5
ywwwy
yywyy
yyyyy
yyyyy
yyyyy
5
wyywy
ywwyy
yyyyy
yyyyy
yyyyy
5
wywyw
ywwwy
yyyyy
yyyyy
yyyyy
5
wwwww
wywyw
ywywy
yyyyy
yyyyy
5
wwwww
wwwww
wyyyw
ywywy
yyyyy
5
wwwww
wwwww
wwyww
wyyyw
ywywy
5
wwwww
wwwww
wwwww
wwwww
ywwwy

*/
点赞
收藏
评论区
推荐文章
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
DaLongggggg DaLongggggg
3年前
python刷题-数列排序
资源限制时间限制:1.0s内存限制:512.0MB问题描述  给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<n<200输入格式  第一行为一个整数n。  第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。输出格式  输出一行,按从小到大的顺序输出排序后的数列。样例输入583649样例输出34689···
Wesley13 Wesley13
3年前
Uber基于RNN的极端事件预测,解决交通问题
时间 2017061212:00:15  亿欧网(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.tuicool.com%2Fsites%2FAJj2Un)_原文_  http://www.iyiou.com/p/47628(https://www.oschina.n
Wesley13 Wesley13
3年前
360笔试
/序列重组时间限制:C/C语言1000MS;其他语言3000MS内存限制:C/C语言65536KB;其他语言589824KB题目描述:在一个古老的国度,这个国家的人并不懂得进位,但是对取模情有独钟,因此诞生了一个经典的问题,给出两个在m进制下含有n位的数字,你可以分别将这两个数各位上的数字重新排列,然
Stella981 Stella981
3年前
Bailian4129 变换的迷宫【BFS】
4129:变换的迷宫(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fbailian.openjudge.cn%2Fpractice%2F4129%3Flang%3Den_US)总时间限制:1000ms内存限制:65536kB描述你现在身处一个R\C的迷
Stella981 Stella981
3年前
Git提交本地以及远程仓库
项目方法Gc75n047Fm3109gDDPJ2006.07.14101007MpkyG专访抖音绽放公会「分享」运营经验(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fhzcya.com%2Fdywh%2F320.html)00azE2
Wesley13 Wesley13
3年前
Cyber
理解计算机的关键,则是要理解计算机背后的人。表面上这是一个机器的时代,但是实际上机器的社记者决定了我们的时代。《黑客与画家》(Hackers&Painters)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fpaulgraham.com%2Fbooks.html)的内容来自
Wesley13 Wesley13
3年前
01背包问题(动态规划求解)
这两天c的习题开始不考察c了,开始考察动态规划问题,唉,没学过动态规划算法来编这题目真是一把辛酸泪,下面给出题目(题目来源:郭玮老师的mooc)2:CharmBracelet查看提交统计提问总时间限制:1000ms内存限制:65536kB描述Bessiehasgonetothemall’s
Stella981 Stella981
3年前
Apache Camel究竟是什么?
问题:_Idon'tunderstandwhatexactlyCamel(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcamel.apache.org%2Findex.html)does._我不明白Camel(https://www.oschina.n
Stella981 Stella981
3年前
Bailian2705 跳绳游戏【序列处理】
2705:跳绳游戏(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fbailian.openjudge.cn%2Fpractice%2F2705%3Flang%3Den_US)总时间限制:1000ms内存限制:65536kB描述小朋友玩跳绳比赛,要计算在一分