题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=598
样例输入:
30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
0 0
样例输出:
Throw 1
1 2 2 4
分析:
这道题可以说是UVa
572 - Oil Deposits的加强版, 先搜出骰子的区域范围,然后再在骰子区域范围里面再搜索出里面有相连的点数数量。
这样的话,可以采用嵌套搜索的方法得解。 这里用DFS,BFS都可以。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char map[60][60];
int vis[60][60];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int w,h,dieNum, dotNum;
struct Node{int x,y; };
Node que[100000];
// 这个搜索用来统计骰子中的相连的点数个数
// 深搜和广搜都可以
void bfs(int x, int y){
int front=0, rear=1;
que[0].x = x, que[0].y = y;
while(front < rear){
Node t = que[front++];
for(int i=0; i<4; ++i){
int dx=t.x+dir[i][0], dy=t.y+dir[i][1];
if(map[dx][dy]=='*' || map[dx][dy]=='.') continue;
if(dx>=0 && dx<h && dy>=0 && dy<w && map[dx][dy]=='X'){
map[dx][dy] = '@'; // 标记为访问过了
Node temp;
temp.x=dx, temp.y=dy;
que[rear++] = temp;
}
}
}
}
// 这个搜索出当前骰子的范围
// 用深搜,广搜都可以,这里用深搜
void dfs(int x,int y){
for(int i=0; i<4; ++i){
int dx=x+dir[i][0], dy=y+dir[i][1];
if(map[dx][dy]=='X'){
++dotNum;
map[dx][dy] = '@';
bfs(dx, dy);
}
if(map[dx][dy]=='.') continue;
if(dx>=0 && dx<h && dy>=0 && dy<w && !vis[dx][dy] && (map[dx][dy]=='*' || map[dx][dy]=='X' || map[dx][dy]=='@')){
vis[dx][dy] = dieNum;
dfs(dx, dy);
}
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int cas=1;
while(~scanf("%d %d%*c",&w,&h) && w && h){
memset(map, 0, sizeof(map));
memset(vis, 0, sizeof(vis));
for(int i=0; i<h; ++i)
gets(map[i]);
dieNum = 1;
vector<int>result;
result.clear();
for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j){
if(map[i][j]=='*' && !vis[i][j]){
vis[i][j] = dieNum;
dotNum = 0;
dfs(i, j);
result.push_back(dotNum);
++dieNum;
}
}
}
printf("Throw %d\n",cas++);
sort(result.begin(), result.begin()+result.size());
if(result[0]!=0){
printf("%d", result[0]);
for(int i=1; i<result.size(); ++i)
printf(" %d",result[i]);
}
printf("\n\n");
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
uva532 Dungeon Master的源代码,并且AC了
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
UVA 10474