• 欢迎光临~

# 2022“杭电杯”（1）补题

## 1002 Dragon slayer（BFS做法）

### 代码实现

``````#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>

#define IOS ios::sync_with_stdio(0),cin.tie(0)

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N = 30 + 10;
int n, m, k;
int path[N], g[N][N], d[N][N];;
int mi, xs, ys, xt, yt;
struct tk {
int x1, x2, y1, y2;
}wall[N];

struct T {
int x, y;
};

//初始化当前的地图
void init() {
memset(g, 0, sizeof g);
memset(d, 0, sizeof d);
d[ys][xs] = 1;
int x1, y1, x2, y2;
for(int i = 1; i <= k; i++) {
if(path[i]) {
x1 = wall[i].x1;
x2 = wall[i].x2;
y1 = wall[i].y1;
y2 = wall[i].y2;
x1 *= 2; x2 *= 2; y1 *= 2; y2 *= 2;
if(x1 == x2) {
for(int i = min(y1,y2); i <= max(y1,y2); i++) {
g[i][x1] = 1;
}
} else if(y1 == y2) {
for(int i = min(x1,x2); i <= max(x1,x2); i++) g[y1][i] = 1;
}
}
}
}

void bfs() {
int now = 0;
for(int i = 1; i <= k; i++) {     //减少无用的bfs，缩短时间
if(path[i] == 0) now++;
if(now >= mi) return ;
}
queue<T> q;
q.push({xs,ys});
init();
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size()) {
T t = q.front();
q.pop();
for(int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if(x >= 0 && y >= 0 && x <= n && y <= m && g[y][x] == 0 && d[y][x] == 0) {
if(x == xt && y == yt) {
mi = now;
return ;
}
q.push({x,y});
d[y][x] = 1;
}
}
}
}

//按二进制递减顺序枚举每面墙存在的情况
void dfway(int u) {
if(u == k + 1) {
bfs();
return ;
}
path[u] = 1;
dfway(u + 1);
path[u] = 0;
dfway(u + 1);
}

void solve() {
cin >> n >> m >> k;
cin >> xs >> ys >> xt >> yt;
n *= 2; m *= 2; xs *= 2; ys *= 2; xt *= 2; yt *= 2;
xs++; ys++; xt++; yt++;
for(int i  = 1; i <= k; i++) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
wall[i] = {x1, x2, y1, y2};
}
mi = k;
dfway(1);
cout << mi << endl;
}

signed main() {
IOS;
int _;
cin >> _;
while(_--) solve();
}
``````