YKpages

ロボット分野で勉強したことのまとめ

AtCoder Regular Contest 005 C - 今日から始める競プロ日記

AtCoder

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Regular Contest 005 C ( ARC 005 C ) 。

実装がちょっと大変で、 もっとスマートに書けるんだろうなーと思いながらコードを書いてた。

C - 器物損壊！高橋君

縦Hマス、横Wマスの街がある。

各マスは'.', '#', 's', 'g'で表されている。

高橋君は 's' から 'g' へ行きたい。

'.' は通ることができる道であり、 '#' は通ることができない塀である。

高橋君は二度まで塀を壊して通ることができる。

このとき、 高橋君は 's' から 'g' へ行くことができるか求めよ。

atcoder.jp

解いた方針

's' マスのコストを0として、 すべてのマスに対してコスト計算を行う。

コストとはそのマスにたどり着くまでに '#' を通った回数。

また、探索中に同じマスを何回も通る可能性があるが、 そのときはコストが小さくなるように更新していく。

そして 'g' マスまでのコストが2以下かどうかを判定する。

2以下ならば 'YES' を出力し、 2より大きいならば 'NO' を出力する。

コード

かなり雑なコードになってしまった。

もっとスマートに書きたい。

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 502;
const int INF = 1<<29;
vector<pair<int, int>> p;
vector<vector<int>> cnt(MAX, vector<int>(MAX, INF));
vector<vector<char>> field(MAX, vector<char>(MAX, '?'));
string ans = "NO";
int sx, sy, gx, gy;
int H, W;
 
// 再帰的にコストを計算していく関数
void func(int x, int y)
{
    // 'g'マスにおいてコストが2以下なら'YES'を出力
    if (x == gx && y == gy && cnt[x][y] <= 2)
    {
        ans = "YES";
        return;
    }
 
    // 上下左右（東西南北）への移動
    for (int i = 0; i < 4; i++)
    {
        // 次のマスの座標を取得
        int nx = x + p[i].first;
        int ny = y + p[i].second;
        // 範囲外なら無効
        if (nx < 0 || nx >= H)
            continue;
        if (ny < 0 || ny >= W)
            continue;
        if (field[nx][ny] == '?')
            continue;
        // 移動先のマスが '#' ならばコスト+1する
        int tmp = cnt[x][y];
        if (field[nx][ny] == '#' && cnt[nx][ny] > tmp+1 && tmp+1 <= 2)
        {
            cnt[nx][ny] = tmp + 1;
            func(nx, ny);
        }
        // 違うならそのままコストを引き継ぐ
        else if (field[nx][ny] != '#' && cnt[nx][ny] > tmp && tmp <= 2)
        {
            cnt[nx][ny] = tmp;
            func(nx, ny);
        }
    }
    return;
}
 
int main()
{
    // 上下左右（東西南北）への移動を定義
    p.push_back(make_pair(0, 1));
    p.push_back(make_pair(0, -1));
    p.push_back(make_pair(1, 0));
    p.push_back(make_pair(-1, 0));
 
    // 入力
    cin >> H >> W;
    for (int x = 0; x < H; x++)
        for(int y = 0; y < W; y++)
            cin >> field[x][y];
 
    // 's' と 'g' マスの座標を取得
    for (int x = 0; x < H; x++)
    {
        for (int y = 0; y < W; y++)
        {
            if (field[x][y] == 's')
            {
                sx = x;
                sy = y;
            }
            else if (field[x][y] == 'g')
            {
                gx = x;
                gy = y;
            }
        }
    }
 
    // 's'マスのコストを0で初期化
    cnt[sx][sy] = 0;
 
    // 's'を起点としてコスト計算
    func(sx, sy);
 
    // 出力
    std::cout << ans << endl;
    return 0;
}

おわりに

実装が大変

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com