首页 > 代码库 > A. The Fault in Our Cubes 暴力dfs
A. The Fault in Our Cubes 暴力dfs
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 = 100 + 2; bool vis[4][4][4]; char str[maxn]; int fx[6] = {0, 1, 0, -1, 0, 0}; int fy[6] = {1, 0, -1, 0, 0, 0}; int fz[6] = {0, 0, 0, 0, -1, 1}; bool check(int x, int y, int z) { if (x < 0 || y < 0 || z < 0) return false; if (x > 2 || y > 2 || z > 2) return false; if (vis[x][y][z]) return false; return true; } int op[22]; 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 == 27) { 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 + 1, tx, ty, tz, dir)) { return true; } else { vis[tx][ty][tz] = false; return false; } } else { vis[tx][ty][tz] = true; for (int i = 0; i < 6; ++i) { if (dir == i || op[dir] == i) continue; if (dfs(cur + 1, tx, ty, tz, i)) { return true; } } vis[tx][ty][tz] = false; return false; } } void work() { op[0] = 2; op[2] = 0; op[1] = 3; op[3] = 1; op[4] = 5; op[5] = 4; scanf("%s", str + 1); for (int i = 2; i <= 26; ++i) { if (str[i] == ‘E‘) { cout << "NO" << endl; return; } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { vis[i][j][k] = true; if (dfs(2, i, j, k, 0)) { 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 0; }
A. The Fault in Our Cubes 暴力dfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。