UVa 657：The die is cast 搜索专题

UVa 657：The die is cast 搜索专题2014-10-16 shuangde800 题目链接：

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 11 2 2 4

分析：

这道题可以说是UVa 572 - Oil Deposits的加强版，先搜出骰子的区域范围，然后再在骰子区域范围里面再搜索出里面有相连的点数数量。

URL：http://www.bianceng.cn/Programming/sjjg/201410/45897.htm

这样的话，可以采用嵌套搜索的方法得解。这里用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 LOCALfreopen（"input.txt","r",stdin）;#endifint 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
",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（"

"）; }return 0;}