题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1175
思路 这种题一想到就用搜索， 但是内存是32m 用 bfs 会不会MLE
没错 第一次 BFS的时候 MLE了 但是加入一些剪枝 就可以过
0.先判断两个位置的棋子是否存在并且相同 1.如果转弯次数 > 2 就不用搜下去 2.如果转弯次数 == 2 那么可以判断一下 从这个点到达终点的路径上 是否还要转弯 如果不是 可以继续判断一下路径上是否存在障碍 如果是 就剪掉
如果还需要 转弯 也可以剪掉
这么剪枝 用DFS 63ms BFS 124ms
然后转弯怎么判断
首先可以发现 如果本来的方向是向上的 那么我们不需要扩展向下走那个方向 因为走了回头路
只需要扩展的是 向上 向左 向右 那么转弯次数 分别为 0 1 1
我们只需要 0 -> up 1 -> right 2 -> down 3 -> left 这样映射起来
那么我们只需要用计算 |当前走的方向-之前走的方向|
如果 为2 就 continue
如果为 3 就是 1 如果为0 或者为1 就是本值
AC代码_BFS
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define L(on) (on<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); #define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e3 + 10; const int MOD = (int)1e9 + 7; int G[maxn][maxn]; int visit[maxn][maxn]; int n, m, q; int sx, sy, ex, ey; int ans; void input() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &G[i][j]); } struct node { int x, y, turn, dir; node () {} node (int x, int y, int turn, int dir) : x(x), y(y), turn(turn), dir(dir) {} }; int Move[4][2] = { -1, 0, 0, 1, 1, 0, 0,-1, }; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || G[x][y]) return false; return true; } bool judge(int x, int y, int dir) // 剪枝 如果turn == 2 并且 这个点到达终点还需要转弯，可以直接剪掉 或者在到达终点的路上存在障碍 也可以剪掉 { if (x != ex && y != ey) return true; if (x == ex) { if (dir == 1) { if (ey < y) return true; else { for (int i = y + 1; i < ey; i++) if (G[x][i]) return true; } } if (dir == 3) { if (ey > y) return true; else for (int i = y - 1; i > ey; i--) if (G[x][i]) return true; } } if (y == ey) { if (dir == 0) { if (ex > x) return true; else for (int i = x - 1; i > ex; i--) if (G[i][y]) return true; } if (dir == 2 && ex < x) { if (ex < x) return true; else for (int i = x + 1; i < ex; i++) if (G[i][y]) return true; } } return false; } void bfs() { queue <node> q; for (int i = 0; i < 4; i++) q.push(node(sx, sy, 0, i)); CLR(visit, 0x3f); visit[sx][sy] = 0; while (!q.empty()) { node u = q.front(); q.pop(); if (u.turn > 2) continue; if (u.turn == 2 && judge(u.x, u.y, u.dir)) continue; for (int i = 0; i < 4; i++) { int nx = u.x + Move[i][0]; int ny = u.y + Move[i][1]; if (ok(nx, ny)) { if (abs(i - u.dir) == 2) continue; int turn = u.turn + (abs(i - u.dir) == 3 ? 1 : abs(i - u.dir)); if (turn < visit[nx][ny]) { visit[nx][ny] = turn; if (nx == ex && ny == ey && turn <= 2) { ans = 1; return; } q.push(node(nx, ny, turn, i)); } } } } return; } int main() { while (scanf("%d%d", &n, &m) && (n || m)) { input(); cin >> q; while (q--) { scanf("%d%d%d%d", &sx, &sy, &ex, &ey); sx--, sy--, ex--, ey--; if (G[sx][sy] && G[ex][ey] && G[sx][sy] == G[ex][ey]) { ans = 0; G[ex][ey] = 0; bfs(); G[ex][ey] = G[sx][sy]; puts(ans ? "YES" : "NO"); } else puts("NO"); } } }AC代码_DFS
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define L(on) (on<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); #define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e3 + 10; const int MOD = (int)1e9 + 7; int G[maxn][maxn]; int visit[maxn][maxn]; int n, m, q; int sx, sy, ex, ey; int ans; void input() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &G[i][j]); } struct node { int x, y, turn, dir; node () {} node (int x, int y, int turn, int dir) : x(x), y(y), turn(turn), dir(dir) {} }; int Move[4][2] = { -1, 0, 0, 1, 1, 0, 0,-1, }; bool ok(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || G[x][y]) return false; return true; } bool judge(int x, int y, int dir) // 剪枝 如果turn == 2 并且 这个点到达终点还需要转弯，可以直接剪掉 或者存在障碍 { if (x != ex && y != ey) return true; if (x == ex) { if (dir == 1) { if (ey < y) return true; else { for (int i = y + 1; i < ey; i++) if (G[x][i]) return true; } } if (dir == 3) { if (ey > y) return true; else for (int i = y - 1; i > ey; i--) if (G[x][i]) return true; } } if (y == ey) { if (dir == 0) { if (ex > x) return true; else for (int i = x - 1; i > ex; i--) if (G[i][y]) return true; } if (dir == 2 && ex < x) { if (ex < x) return true; else for (int i = x + 1; i < ex; i++) if (G[i][y]) return true; } } return false; } void dfs(int x, int y, int turn, int dir) { if (turn > 2 || ans) return; if (x == ex && y == ey) { ans = 1; return; } if (turn == 2 && judge(x, y, dir)) return; for (int i = 0; i < 4 && ans == 0; i++) { if (abs(i - dir) == 2) continue; int tmp = abs(i - dir) == 3 ? 1 : abs(i - dir); int nx = x + Move[i][0]; int ny = y + Move[i][1]; if (ok(nx, ny)) { if (turn + tmp < visit[nx][ny]) { visit[nx][ny] = turn + tmp; dfs(nx, ny, turn + tmp, i); } } } } int main() { while (scanf("%d%d", &n, &m) && (n || m)) { input(); cin >> q; while (q--) { scanf("%d%d%d%d", &sx, &sy, &ex, &ey); sx--, sy--, ex--, ey--; if (G[sx][sy] && G[ex][ey] && G[sx][sy] == G[ex][ey]) { ans = 0; G[ex][ey] = 0; CLR(visit, 0x3f); for (int i = 0; i < 4 && ans == 0; i++) dfs(sx, sy, 0, i); G[ex][ey] = G[sx][sy]; puts(ans ? "YES" : "NO"); } else puts("NO"); } } }转载于:https://www.cnblogs.com/Dup4/p/9433069.html
相关资源：JAVA上百实例源码以及开源项目