UV a 572-Oil Deposits検索テーマ
2972 ワード
572-Oil Deposits
11158
58.77%
5511
95.30%
テーマリンク:
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=105&page=show_problem&problem=513
サンプル入力:
この問題は検索の中で最も基本的な問題の一つと言えます。繋がっているものを探していくなら、いくつありますか?だから、順番に列挙して、@があったら検索して、深く検索して、広く探してもいいです。接続されている@をすべて訪問済みと表記するのが目的です。
DFS(深度検索)とBFS(広域検索)を用いたコードを以下に示す。
コード1:DFS
以上は再帰的にDFSを行うが、データ量が大きいと再帰的にスタックオーバーフローする恐れがある。
以下は再帰的な方式ではなく、アナログスタックの方式でDFSを書く。
11158
58.77%
5511
95.30%
テーマリンク:
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=105&page=show_problem&problem=513
サンプル入力:
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
サンプル出力:0
1
2
2
分析:この問題は検索の中で最も基本的な問題の一つと言えます。繋がっているものを探していくなら、いくつありますか?だから、順番に列挙して、@があったら検索して、深く検索して、広く探してもいいです。接続されている@をすべて訪問済みと表記するのが目的です。
DFS(深度検索)とBFS(広域検索)を用いたコードを以下に示す。
コード1:DFS
#include
#include
#include
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
void dfs(int x, int y){
for(int i=0; i<8; ++i){
int dx=x+dir[i][0], dy=y+dir[i][1];
if(dx>=0 && dx=0 && dy
コード2:以上は再帰的にDFSを行うが、データ量が大きいと再帰的にスタックオーバーフローする恐れがある。
以下は再帰的な方式ではなく、アナログスタックの方式でDFSを書く。
#include
#include
#include
#include
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
struct Node{ int x,y; };
stackst;
void dfs(int x, int y){
while(!st.empty()) st.pop();
Node temp;
temp.x = x, temp.y = y;
st.push(temp);
while(!st.empty()){
temp = st.top();
st.pop();
for(int i=0; i<8; ++i){
int dx=temp.x+dir[i][0], dy=temp.y+dir[i][1];
if(dx>=0 && dx=0 && dy
コード3:BFS#include
#include
#include
using namespace std;
int m,n;
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},
{ 1,0},{1,-1},{0,-1},{-1,-1}};
bool vis[105][105];
char map[105][105];
struct Node{ int x,y; };
Node que[10000];
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<8; ++i){
int dx=t.x+dir[i][0], dy=t.y+dir[i][1];
if(dx>=0 && dx=0 && dy