0

More than 3 years have passed since last update.

posted at

# AtCoder 版！蟻本 (初級編)

この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

## 例題

### 例題 2-1-2 Lake Counting (POJ No.2386)

• 処理はO(N^2)
• 深さ優先探索(dfs)を使用します。
C++
``````#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 100
#define MAX_W 100

int n, m;
string field[MAX_H][MAX_W];

void dfs(int h, int w){
field[h][w] = ".";
for(int dy=-1; dy<=1; dy++){
for(int dx=-1; dx<=1; dx++){
int nx = w+dx;
int ny = w+dy;

if(0<nx && nx<n && 0<ny && ny<m && field[ny][nx] == "W" ){
dfs(ny, nx);
}
}
}
}

int main(int argc, const char * argv[]) {
cin >> n >> m;

for(int h=0; h<n; h++){
for(int w=0; w<n; w++){
cin >> field[h][w];
}
}

int res = 0;
for(int h=0; h<n; h++){
for(int w=0; w<n; w++){
if(field[h][w] == "W"){
dfs(h,w);
res++;
}
}
}

cout << res << endl;

return 0;
}
``````

### A - 深さ優先探索

C++
``````#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 500
#define MAX_W 500

int h, w;
string field[MAX_H][MAX_W];
bool ans = false;

void bfs(int x, int y){
if(field[y][x] == "g") ans = true;

field[y][x] = "#";

for(int d=-1; d<=1; d++){
int nx = x + d;
int ny = y + d;
if(0<=nx&&nx<w){
if(field[y][nx] == "." || field[y][nx] == "g") bfs(nx, y);
}
if(0<=ny&&ny<h){
if(field[ny][x] == "." || field[ny][x] == "g") bfs(x, ny);
}
}
}

int main(int argc, const char * argv[]) {
cin >> h >> w;

for(int y=0; y<h; y++){
string s;
cin >> s;
for(int x=0; x<w; x++){
field[y][x] = s[x];
}
}

for(int y=0; y<h; y++){
for(int x=0; x<w; x++){
if(field[y][x] == "s"){
bfs(x, y);
goto END;
}
}
}

END:
if(ans) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
``````

### B - 埋め立て

C++
``````#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 10
#define MAX_W 10
string field[MAX_H][MAX_W];
bool check_field[MAX_H][MAX_W];
int res = 0;

void dfs(int x, int y){
if(check_field[x][y]) return;
check_field[x][y] = true;

if(x-1>=0 && field[y][x-1]=="o") dfs(x-1, y);
if(x+1<MAX_W && field[y][x+1]=="o") dfs(x+1, y);
if(y-1>=0 && field[y-1][x]=="o") dfs(x, y-1);
if(y+1<MAX_H && field[y+1][x]=="o") dfs(x, y+1);

res++;
}

bool checkField(int x, int y){
if(field[y][x]=="o") return false;

int sum=0;
if(x-1>=0 && field[y][x-1]=="o") sum++;
if(x+1<MAX_W && field[y][x+1]=="o") sum++;
if(y-1>=0 && field[y-1][x]=="o") sum++;
if(y+1<MAX_H && field[y+1][x]=="o") sum++;

if(sum>=2) return true;
return false;
}

int main(int argc, const char * argv[]) {

int sum=0;
for(int i=0; i<MAX_H; i++){
string s;
cin >> s;
for(int j=0; j<MAX_W; j++){
field[i][j] = s[j];
check_field[i][j] = false;
if(s[j] == 'o') sum++;
}
}

for(int i=0; i<MAX_H; i++){
for(int j=0; j<MAX_W; j++){
if(checkField(i, j)){
dfs(i, j);
if(res==sum+1){
cout << "YES" << endl;
goto END;
}else{
for(int i=0; i<MAX_H; i++){
for(int j=0; j<MAX_W; j++){
res=0;
check_field[i][j] = false;
}
}
}
}
}
}

cout << "NO" << endl;
END:

return 0;
}
``````

### B - バウムテスト

• 一度通過した頂点を判定できるようにbool型で保持をする
• for文にて各頂点をから一度も探索した事がない場合に限りdfsを行う。
• dfsにて繋がっている頂点を探索。
• 双方向にて各辺のデータを保持。これをしないと下記のような入力の場合、WAになる。
input
``````5 4
1 5
3 5
3 4
2 4
``````
• 双方向で登録された前回と同じ値は処理を行わない
• 一度通過した頂点がある際は閉路があると判定を行う。
• 最後にdfsを呼び出す
• 計算量はO(n+m)なのでO(n)
C++
``````#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

bool is_cycle=true;
vector<bool> going;

void dfs(vector<vector<int>>& G, int v, int prev_v){
going[v] = true;

for(auto next_v: G[v]){
if(next_v == prev_v) continue;
if(going[next_v]){
is_cycle = false;
continue;
}
dfs(G, next_v, v);
}
}

int main(int argc, const char * argv[]) {
int n, m;
cin >> n >> m;

vector<vector<int>> G(n);
for(int i=0; i<m; i++){
int u, v;
cin >> u >> v;
u--;
v--;
G[u].push_back(v);
G[v].push_back(u);
}

going.assign(n, false);

int res=0;
for(int i=0; i<n; i++){
if(!going[i]){
is_cycle = true;
dfs(G, i, -1);
if(is_cycle) res++;
}
}

cout << res << endl;
return 0;
}
``````

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
What you can do with signing up
0