输入案例 (注意ZOJ 上给的输入案例有问题,直接复制输入,输出答案不是 1224,以下是我按题目描述自定义的输入案例)
30 15
输出案例:
Throw 1
1 2 2 4
<—空行—>
题目大意:
自己机器翻译吧~~~
解题思路:
每一个点都进行遍历,如果遇到 ‘.’ 就直接跳过,如果遇到 ‘*’ 则把 ‘*’ 转换成 ‘.’ (即消除’*’),并且dfs搜索共边的所有’*’,到达边界或者遇到 ‘.’ 则停止搜索。如果遇到 ‘X’ 则先转换成 ‘*’ 再转换成 ‘.’(消除 ‘X’),并且也是dfs搜索共边的所有 ‘X’,到达边界或者没遇到 ‘X’ 则停止搜索。可能回问为什么要转换两次,直接 ‘X’ 转换成 ‘.’ 不香嘛? 仔细想想如果直接把 ‘X’ 转换成 ‘.’ 岂不是把一个骰子变成了两个骰子,这是不允许的。
使用两次 DFS 即可解决这道题
实现代码:
/*
* ZJU_1191-The Die Is Cast
*
* */
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_CAPACITY 51 // 定义最大容量
char image[MAX_CAPACITY][MAX_CAPACITY]; // 图片数据
int w,h; // 定义长宽
int sum = 0; // 一个骰子的点数
// 骰子上的点数的像素转化为骰子像素背景,dfs 搜索
void dots(int j, int k) {
// 结束标志, 1.到达图片的边界 2. 上下左右都没遇到 'X' 说明当前骰子的一个点已经确认
if (j < 0 || j >= h || k < 0 || k >=w || image[j][k] != 'X') return;
// 像素转换,消除 'X'
image[j][k] = '*';
// 上下左右深度搜索共边的像素
dots(j-1, k);
dots(j+1,k);
dots(j, k-1);
dots(j,k+1);
}
// 骰子像素转化成图片背景,dfs深度搜索
void dice(int j, int k) {
// 结束标志, 1.到达图片的边界 2. 遇到 '.' 说明当前骰子的边界到了
if (j < 0 || j >= h || k < 0 || k >=w || image[j][k] == '.') return;
// 如果遇到骰子中的像素是点,这统计点的个数
if (image[j][k] == 'X') {
// 点的个数加一
sum++;
// 骰子点数像素转化为骰子像素
dots(j,k);
}
// 像素转换. 消除 '*'
image[j][k] = '.';
// 上下左右深度搜索共边的像素
dice(j-1, k);
dice(j+1,k);
dice(j, k-1);
dice(j,k+1);
}
int main() {
int num[MAX_CAPACITY*MAX_CAPACITY];
int number = 1; // 记录第几次投郑骰子
int count; // 记录骰子个数
while (cin>>w>>h && (w||h)) {
count = 0; // 记录
for (int i = 0; i < h; ++i)
cin>>image[i]; // 存储二维数组中
for (int j = 0; j < h; ++j) {
for (int k = 0; k < w; ++k) {
if (image[j][k] == '.') continue; // 遇到背景像素跳过
sum = 0;
if (image[j][k] == '*') dice(j,k);// 骰子像素转化为背景像素, j,k 像素坐标
else if (image[j][k] == 'X') {
// 点的个数加一
sum++;
// X 转换成 *
dots(j,k);
// * 转换成 .
dice(j,k);
};
num[count++] = sum; // 保存骰子的点数
}
}
// 将所有骰子的点数排序
sort(num,num+count);
// 输出答案
cout<<"Throw "<<number++<<endl;
if (count > 0) cout<<num[0];
for (int l = 1; l < count; ++l) {
cout<<" "<<num[l];
}
cout<<endl;
}
return 0;
}