1.链接地址:
http://bailian.openjudge.cn/practice/2813
http://poj.org/problem?id=1681
2.题目:
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 有一个正方形的墙,由N*N个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画 笔不好使。当他用画笔涂画第(i, j)个位置的砖时, 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。
- 输入
- 第一行是个整数t(1≤t ≤20),表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n (1≤n
≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白
砖,“y”表示黄砖。- 输出
- 每个案例输出一行。如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
- 样例输入
2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww- 样例输出
0
15- 来源
- 1681
3.思路:
此题思路与 OpenJudge 2811 熄灯问题 和 Poj 1222 EXTENDED LIGHTS OUT 一样,请查看以下
http://www.cnblogs.com/mobileliker/p/3548190.html
注意此题的区别是有可能出现不存在的情况,所以要多一个判断
4.代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring> using namespace std; int main()
{
int i,j; int t;
cin>>t; int n;
int flag;
while(t--)
{
flag = ;
cin>>n; bool *arr_draw = new bool[(n + ) * (n + )];
bool *arr_draw_save = new bool[(n + ) * (n + )];
bool *arr_res = new bool[(n + ) * (n + )]; string str;
memset(arr_draw,,sizeof(bool) * (n + ) * (n + ));
for(i = ; i <= n; ++i)
{
cin>>str;
for(j = ; j <= n; ++j)
{
if(str[j-] == 'y') arr_draw[i * (n + ) + j] = false;
else arr_draw[i * (n + ) + j] = true;
}
}
memcpy(arr_draw_save,arr_draw,sizeof(bool) * (n + ) * (n + )); memset(arr_res + * (n + ),,sizeof(bool) * (n + ));
while()
{
for(i = ; i <= n; ++i)
{
for(j = ; j <= n; ++j)
{
arr_draw[(i - ) * (n + ) + j] ^= arr_res[i * (n + ) + j];
arr_draw[i * (n + ) + (j - )] ^= arr_res[i * (n + ) + j];
arr_draw[i * (n + ) + (j + )] ^= arr_res[i * (n + ) + j];
arr_draw[(i + ) * (n + ) + j] ^= arr_res[i * (n + ) + j];
arr_draw[i * (n + ) + j] ^= arr_res[i * (n + ) + j];
}
memcpy(&arr_res[(i + ) * (n + )],&arr_draw[i * (n + )],sizeof(bool) * (n + ));
}
for(i = ; i <= n; ++i) if(arr_draw[n * (n + ) + i]) break;
if(i > n) break;
else
{
memcpy(arr_draw,arr_draw_save,sizeof(bool) * (n + ) * (n + )); for(i = n; i > ; --i) if(!arr_res[ *(n + ) + i]) break;
while(i <= n) {arr_res[ * (n + ) + i] = !arr_res[ * (n + ) + i]; ++i;} for(i = ; i <= n; ++i) {if(arr_res[ * (n + ) + i]) break;}
if(i > n) {flag = ; break;}
}
} int count = ;
if(flag)
{
for(i = ; i <= n; ++i)
{
for(j = ; j <= n; ++j)
{
count += arr_res[i * (n + ) + j];
}
}
cout<<count<<endl;
}
else cout<<"inf"<<endl; delete [] arr_draw;
delete [] arr_draw_save;
delete [] arr_res; }
return ;
}