题目链接:Problem - 7139 (hdu.edu.cn)
题目 / Problem
给定一个N x M的地图和K堵墙(N, M, K <= 15),注意这里的墙在方格的边缘而非方格内,需要进行移动判定。
给一个起点(sx, sy)和终点(fx, fy)。
问最少移除几道墙可以从起点走到终点。
思路 / Thought
做题往往从数据范围小的变量入手,比如本题的K。
因为K很小,2的15次方也才不过3e4左右,所以我们完全可以枚举出墙的所有开合情况,用一个数字u的各个二进制位表示某堵墙是否被推倒,再验证这种情况的起点和终点是否连通,若连通就更新答案。
复杂度为O(N * M * 2 ^ K),最大是1e7左右,很健康的复杂度。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 20; int sx, sy, fx, fy, N, M, K; bitset<maxn> vis[maxn], col[maxn], row[maxn]; struct Wall { int x1, y1, x2, y2; }w[maxn]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int lowbit(int x){return x & -x;} int getcnt(int x) { int res = 0; while(x)x -= lowbit(x), res ++; return K - res; } bool judge(int x,int y,int dir)//判断某点往dir方向是否可行 { if(dir == 0)return !(col[x][y + 1] && col[x + 1][y + 1]); else if(dir == 1)return !(col[x][y] && col[x + 1][y]); else if(dir == 2)return !(row[x + 1][y] && row[x + 1][y + 1]); else if(dir == 3)return !(row[x][y] && row[x][y + 1]); return 0; } bool dfs(int x, int y) { vis[x][y] = 1; if(x == fx && y == fy)return 1; for(int i = 0;i < 4; ++ i) { int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx >= N || ny < 0 || ny >= M || vis[nx][ny])continue; if(judge(x, y, i) && dfs(nx, ny))return 1; } return 0; } bool check(int u) { for(int i = 0;i <= N; ++ i) { vis[i].reset(); col[i].reset(); row[i].reset(); } for(int i = 0;i < K; ++ i) { if(u & 1) { int x1 = w[i].x1, y1 = w[i].y1, x2 = w[i].x2, y2 = w[i].y2; if(x1 == x2) { if(y1 >= y2)swap(y1, y2); for(int i = y1;i <= y2; ++ i)row[x1][i] = 1; } else if(y1 == y2) { if(x1 >= x2)swap(x1, x2); for(int i = x1;i <= x2; ++ i)col[i][y1] = 1; } } u >>= 1; } return dfs(sx, sy); } void solve() { cin >> N >> M >> K; cin >> sx >> sy >> fx >> fy; for(int i = 0;i < K; ++ i)cin >> w[i].x1 >> w[i].y1 >> w[i].x2 >> w[i].y2; int ans = K; for(int u = 0;u < (1 << K); ++ u)//u表示墙的开合状态 if(check(u))ans = min(ans, getcnt(u)); cout << ans << '\n'; } signed main() { int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING