http://codeforces.com/gym/101257/problem/A

把它固定在(0,0, 0)到(2, 2, 2)上,每次都暴力dfs检查,不会超时的,因为规定在这个空间上,一不行,就会早早退出。

这样写起来比较好写。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = + ;
bool vis[][][];
char str[maxn];
int fx[] = {, , , -, , };
int fy[] = {, , -, , , };
int fz[] = {, , , , -, };
bool check(int x, int y, int z) {
if (x < || y < || z < ) return false;
if (x > || y > || z > ) return false;
if (vis[x][y][z]) return false;
return true;
}
int op[];
bool dfs(int cur, int x, int y, int z, int dir) {
int tx = fx[dir] + x, ty = fy[dir] + y, tz = fz[dir] + z;
if (cur == ) {
if (check(tx, ty, tz)) return true;
else return false;
}
if (!check(tx, ty, tz)) return false;
if (str[cur] == 'I') {
vis[tx][ty][tz] = true;
if (dfs(cur + , tx, ty, tz, dir)) {
return true;
} else {
vis[tx][ty][tz] = false;
return false;
}
} else {
vis[tx][ty][tz] = true;
for (int i = ; i < ; ++i) {
if (dir == i || op[dir] == i) continue;
if (dfs(cur + , tx, ty, tz, i)) {
return true;
}
}
vis[tx][ty][tz] = false;
return false;
}
}
void work() {
op[] = ;
op[] = ;
op[] = ;
op[] = ;
op[] = ;
op[] = ;
scanf("%s", str + );
for (int i = ; i <= ; ++i) {
if (str[i] == 'E') {
cout << "NO" << endl;
return;
}
}
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
for (int k = ; k < ; ++k) {
vis[i][j][k] = true;
if (dfs(, i, j, k, )) {
cout << "YES" << endl;
return;
}
vis[i][j][k] = false;
}
}
}
cout << "NO" << endl;
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}
04-17 22:55