Codeforces Good Bye 2017: B. New Year and Buggy Bot

,

http://codeforces.com/contest/908/problem/B

problem

障害物の置かれた盤面と数列が与えられる。 数から方向への対応$\sigma \in \mathfrak{S}_4$を固定し、数列から翻訳された方向に従ってロボットが動く。 ロボットがスタートからゴールまで移動できるような対応の数はいくつか。

solution

全部試す。$4!$が定数に乗る$O(HW + |s|)$。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;

const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };

int main() {
    // input
    int h, w; cin >> h >> w;
    vector<string> f(h);
    REP (y, h) cin >> f[y];
    string command; cin >> command;
    // solve
    int sy = -1;
    int sx = -1;
    REP (y, h) REP (x, w) {
        if (f[y][x] == 'S') {
            sy = y;
            sx = x;
        }
    }
    int cnt = 0;
    array<int, 4> mapping;
    iota(ALL(mapping), 0);
    do {
        int y = sy;
        int x = sx;
        for (char c : command) {
            int dir = mapping[c - '0'];
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (ny < 0 or h <= ny or nx < 0 or w <= nx) break;
            if (f[ny][nx] == '#') break;
            y = ny;
            x = nx;
            if (f[y][x] == 'E') break;
        }
        cnt += f[y][x] == 'E';
    } while (next_permutation(ALL(mapping)));
    // output
    printf("%d\n", cnt);
    return 0;
}