Codeforces Good Bye 2017 B. New Year and Buggy Bot 枚举全排列、模拟

My Solution

题意：给出一张地图，有一个出口和入口，以及一些障碍和通道。然后给出一个操作序列0123，分别表示上下左右，

求有多少种对应的可能可以使得按照该指令序列从入口走到出口。0->下，1->左，2->上，3->右为一种可能，以此类推。

枚举全排列、模拟

我们规定长度为4的序列op，op0表示上，op1表示下，op2表示左，op3表示右。

所以只要枚举0123的全排列即可得到所以的对应可能，然后用每一个排列去模拟的跑一遍地图即可判断该情况是否可行。

/*//枚举全排列代码

inline void dfs(int u){
int i, j, ok;
if(u == 4){
;//
return;
}

for(i = 0; i < 4; i++){
ok = 1;
for(j = 0; j < u; j++){
if(op[j] == i) ok = 0;
}
if(ok){
op[u] = i;
dfs(u+1);
}
}
}

*/

时间复杂度 O（4！ * n）

空间复杂度 O（n）

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 50 + 8;

string mp[MAXN], s;
int v[108], op[4];
int ans, sx, sy, ex, ey, sz, n, m;

inline void dfs(int u){
    int i, j, ok;
    if(u == 4){
        int x = sx, y = sy, ptr;
        for(i = 0; i < sz; i++){
            for(j = 0; j < 4; j++){
                if(op[j] == v[i]){
                    ptr = j;
                }
            }
            if(ptr == 0){
                x -= 1;
            }
            else if(ptr == 1){
                x += 1;
            }
            else if(ptr == 2){
                y -= 1;
            }
            else{
                y += 1;
            }
            if(y < 0 || y >= m || x < 0 || x >= n){
                return;
            }
            if(mp[x][y] == '#') return;
            if(mp[x][y] == 'E'){
                ans++; return;
            }
        }

        return;
    }

    for(i = 0; i < 4; i++){
        ok = 1;
        for(j = 0; j < u; j++){ if(op[j] == i) ok = 0; } if(ok){ op[u] = i; dfs(u+1); } } } int main() { #ifdef LOCAL freopen("b.txt", "r", stdin); //freopen("b.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int i, j; ans = 0; cin >> n >> m;
    for(i = 0; i < n; i++){ cin >> mp[i];
    }
    cin >> s;
    sz = s.size();
    for(i = 0; i < sz; i++){
        v[i] = s[i] - '0';
    }
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            if(mp[i][j] == 'S'){
                sx = i;
                sy = j;
            }
            else if(mp[i][j] == 'E'){
                ex = i;
                ey = j;
            }
        }
    }

    //op[0] = -1, op[1] = -1, op[2] = -1, op[3] = -1;
    dfs(0);
    cout << ans << endl;



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

                                                                                                                                             ------from ProLightsfx