Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@Parascorpaena

【分野別　初中級者が解くべき過去問精選 100 問】を初級者がC++で解く【幅優先探索】

Posted at

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の2-3. 分野別　初中級者が解くべき過去問精選 100 問を初級者がC++で解いていきます。

幅優先探索

28　ALDS_11_C - 幅優先探索

AIZU ONLINE JUDGE に登録していないので、後回し。

29　AtCoder Beginner Contest 007 C - 幅優先探索

お手本通りにBFSで最短経路を探す。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int R, C;
  cin >> R >> C;
  
  int sy, sx, gy, gx;
  cin >> sy >> sx >> gy >> gx;
  sy--; sx--; gy--; gx--;
  
  vector<vector<char>> G(R, vector<char>(C));
  rep(r, 0, R) {
    rep(c, 0, C) {
      cin >> G.at(r).at(c);
    }
  }
  
  queue<pair<int, int>> que;
  que.push({sy, sx});
  
  vector<vector<int>> dist(R, vector<int>(C, -1));
  dist.at(sy).at(sx) = 0;
  
  vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
  
  while(!que.empty()) {
    pair<int, int> pr = que.front();
    que.pop();
    int y = pr.first;
    int x = pr.second;
    
    rep(i, 0, 4) {
      int ny = y + dy.at(i);
      int nx = x + dx.at(i);
      
      if (ny < 0 || R <= ny || nx < 0 || C <= nx) continue;
      if (G.at(ny).at(nx) == '#') continue;
      if (dist.at(ny).at(nx) != -1) continue;
      
      dist.at(ny).at(nx) = dist.at(y).at(x) + 1;
      que.push({ny, nx});
    }
  }
  cout << dist.at(gy).at(gx) << endl;
}

30　JOI 2011 予選 5 - チーズ

「次のチーズまでBFSで最短経路を探す」を繰り返してチーズNにたどり着いたら終わり。各距離の合計が答え。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  
  vector<vector<char>> G(H, vector<char>(W));
  int sh, sw;
  rep(h, 0, H) {
    rep(w, 0, W) {
      char c;
      cin >> c;
      
      if (c == 'S') {
        sh = h;
        sw = w;
      }
      
      G.at(h).at(w) = c;
    }
  }
  
  vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
  int ans = 0;
  
  rep(n, 1, N + 1) {    
    vector<vector<int>> dist(H, vector<int>(W, -1));
    dist.at(sh).at(sw) = 0;
    
    queue<pair<int, int>> que;
    que.push({sh, sw});
    
    while (!que.empty()) {
      bool is_break = false;
      
      pair<int, int> pr = que.front();
      que.pop();
      int x = pr.first;
      int y = pr.second;

      rep(i, 0, 4) {
        int nx = x + dx.at(i);
        int ny = y + dy.at(i);
        
        if (nx < 0 || H <= nx || ny < 0 || W <= ny) continue;
        if (G.at(nx).at(ny) == 'X') continue;
        if (dist.at(nx).at(ny) != -1) continue;
        
        dist.at(nx).at(ny) = dist.at(x).at(y) + 1;
        que.push({nx, ny});
        
        if (G.at(nx).at(ny) == (char) n + '0') {
          is_break = true;
          sh = nx;
          sw = ny;
          break;
        }
      }
      if (is_break) break;
    }
    ans += dist.at(sh).at(sw);
  }
  cout << ans << endl;
}

31　JOI 2012 予選 5 - イルミネーション

マスが六角形になった途端に実装がぐちゃぐちゃになってしまって解けなかった。解けなかった原因は、地図を囲むように塗りつぶす(公式解説)という発想に至らなかったこと。
壁の数え方も悩んだけど、ふつうに建物外から建物にぶつかったらそこが壁なので、答えをインクリメントすればいいだけだった。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int W, H;
  cin >> W >> H;
  
  vector<vector<int>> G(H + 2, vector<int>(W + 2, 0));
  rep(i, 1, H + 1) {
    rep(j, 1, W + 1) {
      cin >> G.at(i).at(j);
    }
  }
  
  queue<pair<int, int>> que;
  que.push({0, 0});
  
  vector<vector<int>> dist(H + 2, vector<int>(W + 2, 0));
  dist.at(0).at(0) = 1;
  
  vector<int> dx(6), dy(6);
  
  int ans = 0;
  
  while(!que.empty()) {
    pair<int, int> pr = que.front();
    que.pop();
    int x = pr.first;
    int y = pr.second;
    
    if (y % 2 == 0) {
      dx = {-1, 0, 1, 0, -1, -1};
      dy = {-1, -1, 0, 1, 1, 0};
    }
    else {
      dx = {0, 1, 1, 1, 0, -1};
      dy = {-1, -1, 0, 1, 1, 0};
    }
    
    rep(i, 0, 6) {
      int nx = x + dx.at(i);
      int ny = y + dy.at(i);
      
      if (nx < 0 || W + 2 <= nx || ny < 0 || H + 2 <= ny) continue;
      if (G.at(ny).at(nx) == 1) {
        ans++;
        continue;
      }
      if (dist.at(ny).at(nx) != 0) continue;
      
      dist.at(ny).at(nx) = dist.at(y).at(x) + 1;
      que.push({nx, ny});
    }
  }
  cout << ans << endl;
}

32　AOJ 1166 - 迷図と命ず

AIZU ONLINE JUDGE に登録していないので、後回し。

33　AtCoder Beginner Contest 088 D - Grid Repainting

「黒いマスに変えられる最大値を求める」ということは「白いマスの最小値を求める」ことと同じで、それはつまり「スタートからゴールまでの最短経路を求める」ということ。BFSで最短経路を求めて、通らなかったマスが黒に変えられるマスになる。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
const ll inf = 1LL << 60;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repeq(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, b, a) for (int i = b; i >= a; i--)
#define repb(i, n) for (int i = 0; i < (1 << n); i++)
#define fore(i, n) for (auto &i : n)
#define all(x) x.begin(), x.end()
template<class T>bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if (a > b) {a = b; return 1;} return 0;}

int main() {
  int H, W;
  cin >> H >> W;
  
  int white = 0;
  vector<vector<char>> G(H, vector<char>(W));
  rep(i, 0, H) {
    rep(j, 0, W) {
      char g;
      cin >> g;
      
      if (g == '.') white++;
      G.at(i).at(j) = g;
    }
  }
  
  queue<pair<int, int>> que;
  que.push({0, 0});
  
  vector<vector<int>> dist(H, vector<int>(W, 0));
  dist.at(0).at(0) = 1;
  
  vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
  
  while(!que.empty()) {
    pair<int, int> pr = que.front();
    que.pop();
    int x = pr.first;
    int y = pr.second;

    rep(i, 0, 4) {
      int nx = x + dx.at(i);
      int ny = y + dy.at(i);
      
      if (nx < 0 || W <= nx || ny < 0 || H <= ny) continue;
      if (G.at(ny).at(nx) == '#') continue;
      if (dist.at(ny).at(nx) != 0) continue;
      
      dist.at(ny).at(nx) = dist.at(y).at(x) + 1;
      que.push({nx, ny});
    }
  }
  
  if (dist.at(H - 1).at(W - 1) == 0) cout << -1 << endl;
  else cout << white - dist.at(H - 1).at(W - 1) << endl;
}

0
1
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
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?