蟻本　迷路の最短路

@drkenさんの[AtCoder 版！蟻本 (初級編)](https://qiita.com/drken/items/e77685614f3c6bf86f44#2-1-%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E5%9F%BA%E6%9C%AC-%E5%85%A8%E6%8E%A2%E7%B4%A2)の迷路の最短路の類題を触って見ました

##ABC007_C

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using Graph = vector<vector<int>>;

int R,C;
int sy,sx,gy,gx;
char c [60][60];

int main(){
    cin >> R >> C;
    cin >> sy >> sx >> gy >> gx;
    sy--; sx--; gy--; gx--;
    rep(i,R){
        rep(j,C){
            cin >> c[i][j];
        }
    }
    queue<pair<int,int>> > q;
    q.push(make_pair(sy,sx));
    vector<vector<int>> d(60,vector<int>(60));
    d[sy][sx] = 0;
    while ( !q.empty()){
        pair<int,int> now = q.front();
        q.pop();
        int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
        rep(i,4){
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if(ny < 0 || R <= ny || nx < 0 || C <= nx || d[ny][nx] == '#' || d[nx][ny] != -1){
                continue;
            }
            d[ny][nx] = d[now.first][now.second] + 1;
            q.push(make_pair(ny,nx));
        }
    }
    cout << d[gy][gx] << endl;
}

##ABC088_D

```c++

#include <bits/stdc++.h>
using namespace std;

int h, w;
char s[55][55];
int dist[55][55];
queue <pair<int, int>> q;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    cin >> h >> w;
    int all = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> s[i][j];
            if (s[i][j] == '.') all++;
        }
    }
    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) dist[i][j] = -1;
    }
    dist[1][1] = 0;
    q.push(make_pair(1, 1));
    while (!q.empty()) {
        pair<int,int> v = q.front();
        q.pop();
        int x = v.first;
        int y = v.second;
        for (int k = 0; k < 4; k++) {
            int tox = x + dx[k];
            int toy = y + dy[k];
            if (1 <= tox && tox <= h && 1 <= toy && toy <= w) {
                if (s[tox][toy] == '#') continue;
                if (dist[tox][toy] != -1) continue;
                dist[tox][toy] = dist[x][y] + 1;
                q.push(make_pair(tox, toy));
            }
        }
    }
    if (dist[h][w] == -1) {
        cout << -1;
    }
    else {
        cout << all - dist[h][w] - 1;
    }
    return 0;
}

```

##ABC088_D
```c++

#include <bits/stdc++.h>
using namespace std;

int h, w;
char s[55][55];
int dist[55][55];
queue <pair<int, int>> q;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
    cin >> h >> w;
    int all = 0;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> s[i][j];
            if (s[i][j] == '.') all++;
        }
    }
    for (int i = 1; i <= 50; i++) {
        for (int j = 1; j <= 50; j++) dist[i][j] = -1;
    }
    dist[1][1] = 0;
    q.push(make_pair(1, 1));
    while (!q.empty()) {
        pair<int,int> v = q.front();
        q.pop();
        int x = v.first;
        int y = v.second;
        for (int k = 0; k < 4; k++) {
            int tox = x + dx[k];
            int toy = y + dy[k];
            if (1 <= tox && tox <= h && 1 <= toy && toy <= w) {
                if (s[tox][toy] == '#') continue;
                if (dist[tox][toy] != -1) continue;
                dist[tox][toy] = dist[x][y] + 1;
                q.push(make_pair(tox, toy));
            }
        }
    }
    if (dist[h][w] == -1) {
        cout << -1;
    }
    else {
        cout << all - dist[h][w] - 1;
    }
    return 0;
}

```

##AGC033_A

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using pii = pair<int,int>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };

int main() {
    int H, W;
    cin >> H >> W;
    char A[1010][1010];
    queue <pair<pii,int>>q;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
            if (A[i][j] == '#') {
                q.push({ {i,j},0 });
            }
        }
    }
    int ans = 0;
    while (!q.empty()) {
        auto key = q.front();
        ans = max(ans, key.second);
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int ny = key.first.first + dy[i];
            int nx = key.first.second + dx[i];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W||A[ny][nx]=='#') {
                continue;
            }
            else {
                A[ny][nx] = '#';
                q.push({ { ny,nx }, key.second + 1 });
            }
        }
    }
    cout << ans << endl;
    return 0;
}
```

##ARC005_C

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using pii = pair<int,int>;
const int INF = 1e9;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

int H,W;
char C[510][510];
int sy,sx,gy,gx;
int d[510][510];

int main(){
    cin >> H >> W;
    rep(i,H){
        rep(j,W){
            cin >> C[i][j];
            if(C[i][j] == 's')sy = i,sx = j;
            if(C[i][j] == 'g')gy = i,gx = j;
            d[i][j] = INF;
        }
    }
    deque<pii> q;
    q.push_back({sy,sx});
    d[sy][sx] = 0;
    while (q.size()){
        pii p;
        p = q.front();
        int y = p.first;
        int x = p.second;
        q.pop_front();
        rep(i,4){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= 0 && ny < H && nx >= 0 && nx < W){
                bool wall = (C[y][x] == '#');
                int d2 = d[y][x] + wall;
                if(d[ny][nx] > d2){
                    d[ny][nx] = d2;
                    if (wall) {
                        q.push_back({ny,nx});
                    }
                    else {
                        q.push_back({ny,nx});
                    }
                }
            }
        }
    }
    if (d[gy][gx] <= 2){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}

```

###感想
今回は、BFSというもの勉強しました。時間をかなりかけましたが自分なりに使い方を理解できたと思います。