UVa 657-The die is cast 검색 테마
4643 단어 cast
5159
24.66%
1357
70.23%
제목 링크:
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
",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;
}
-생명의 의 미 는 그 에 게 의 미 를 부여 하 는 데 있다.
오리지널
http://blog.csdn.net/shuangde800
,By D_Double
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UnrealC++로 구조체(USTURCT)를 캐스트해 보기리플렉션이란 런타임시 프로그램의 구조(클래스의 상속 관계나 어떤 함수나 변수를 가지고 있는지 등...) 취득하거나 설정하거나 할 수 있는 구조입니다. 표준 C++에는 현재 리플렉션 기능이 없지만 UnrealC++에는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.