0x25
推箱子。。。。。。。 是真的写废了。。。。
矩阵距离
这个就是常见点 一开始就把多元点 放入队列的写法
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
typedef pair<int, int> P;
int n, m;
int ans[maxn][maxn];
struct node{
int x, y, st;
};
queue<node> que;
bool chk(int x, int y) {
return (x < 1 || y < 1 || x > n || y > m || ans[x][y] != -1);
}
void bfs(){
while(!que.empty()){
node p = que.front(); que.pop();
for(int i = 0; i < 4; i ++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
if(chk(nx, ny)) continue;
ans[nx][ny] = p.st + 1;
que.push(node{nx, ny, p.st + 1});
}
}
}
int main(){
memset(ans, -1, sizeof ans);
cin >> n >> m;
string str;
for(int i = 1;i <= n; i ++) {
cin >> str;
for(int j = 1; j <= m; j ++) {
if(str[j - 1] == '1') ans[i][j] = 0, que.push(node{i, j, 0});
}
}
bfs();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j ++) cout << ans[i][j] << " ";
cout << endl;
}
return 0;
}
0x26
双端队列BFS
电路维修 权值只有 0 1 0 放前面提前出 1 放后面 以此减低复杂度
注意 每个点 对应的权值 改了好就
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int maxn = 505;
const int dx[] = {1, -1, -1, 1};
const int dy[] = {1, -1, 1, -1};
const int ndx[] = {1, 0, 0, 1};
const int ndy[] = {1, 0, 1, 0};
int n, m;
char str[maxn][maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn];
struct node{
int x, y;
};
bool check(int x, int y) {return x >= 0 && x <= n && y >= 0 && y <= m;}
void bfs(){
deque<node> que;
que.push_back(node{0, 0});
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
vis[0][0] = 1;
dis[0][0] = 0;
while(!que.empty()) {
node p = que.front(); que.pop_front();
for(int i = 0, t; i < 4; i ++) {
int nx = p.x + ndx[i], tx = p.x + dx[i];
int ny = p.y + ndy[i], ty = p.y + dy[i];
if(i < 2) t = str[nx][ny] == '/' ? 1 : 0;
else t = str[nx][ny] == '/' ? 0 : 1;
if(check(tx, ty) && !vis[tx][ty] && dis[tx][ty] > dis[p.x][p.y] + t){
dis[tx][ty] = dis[p.x][p.y] + t;
if(t) que.push_back(node{tx, ty});
else que.push_front(node{tx, ty});
}
}
}
if(dis[n][m] != 0x3f3f3f3f) cout << dis[n][m] << endl;
else cout << "NO SOLUTION" << endl;
}
int main(){
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> (str[i] + 1);
bfs();
// for(int i = 0; i <= n; i ++) {
// for(int j = 0; j <= m; j++) {
// cout << dis[i][j] << " ";
// }cout << endl;
// }
}
return 0;
}
优先队列BFS
我想起了DJ最短路。。
Full Tank
这个 也是常见的 很像最短路 分层图一个写法
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
int head[maxn], fcst[maxn], cnt;
int nxt[maxn * 20], to[maxn * 20], dis[maxn * 20];
bool vis[maxn][105];
struct node{
int u, f, cst;
bool operator < (const node & a) const {
return cst > a.cst;
}
};
void ade(int a, int b, int v) {
to[++cnt] = b, dis[cnt] = v;
nxt[cnt] = head[a], head[a] = cnt;
to[++cnt] = a, dis[cnt] = v;
nxt[cnt] = head[b], head[b] = cnt;
}
int dj(int c, int s, int t){
priority_queue<node> que;
memset(vis, 0, sizeof vis);
que.push(node{s, 0, 0});
while(!que.empty()) {
node p = que.top(); que.pop();
if(p.u == t) return p.cst;
if(vis[p.u][p.f]) continue;
vis[p.u][p.f] = 1;
if(p.f < c && !vis[p.u][p.f + 1]) {
que.push(node{p.u, p.f + 1, p.cst + fcst[p.u]});
}
for(int i = head[p.u]; i; i = nxt[i]) {
int v = to[i];
if(p.f >= dis[i] && !vis[v][p.f - dis[i]]) {
que.push(node{v, p.f - dis[i], p.cst});
}
}
}
return -1;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++) cin >> fcst[i];
for(int i = 1, a, b, c; i <= m; i ++)
cin >> a >> b >> c, ade(a, b, c);
cin >> m;
for(int i = 1, c, s, t; i <= m; i ++) {
cin >> c >> s >> t;
int ans = dj(c, s, t);
if(ans == -1) cout << "impossible\n";
else cout << ans << endl;
}
return 0;
}
双向BFS
噩梦
对着3个会动的分别极限BFS 每个人论者进行一次 鬼先走
省去去 一起跑 状态太多的存储 也是BFS一个有效方法
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 800 + 5;
const int INF = 0x3f3f3f3;
const int cx[] = {-1, 0, 1, 0};
const int cy[] = {0, 1, 0, -1};
string str;
int n, m, cas;
char mp[maxn][maxn];
struct node{
int x, y, sp;
node(int _x, int _y, int _sp){
x = _x, y = _y, sp = _sp;
}
};
queue<node> G, Z, M;
bool chkZ(int x, int y) {
return (x < 1 || y < 1 || x > n || y > m || mp[x][y] == 'Z');
}
bool chkH(int x, int y) {
if((x < 1 || y < 1 || x > n || y > m)) return 1;
if(mp[x][y] == 'X' || mp[x][y] == 'Z') return 1;
return 0;
}
void pt(){
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j ++) {
cout << mp[i][j] << " ";
}cout << endl;
}
}
int sol(){
while(Z.size()) {
int time = Z.front().sp;
// cout << "-----------" << endl;pt();cout << endl;
while(!Z.empty() && Z.front().sp < time + 2) {
node p = Z.front(); Z.pop();
for(int i = 0; i < 4; i ++) {
int nx = p.x + cx[i], ny = p.y + cy[i];
if(chkZ(nx, ny)) continue;
mp[nx][ny] = 'Z';
Z.push(node(nx, ny, p.sp + 1));
}
}
// pt();cout << endl;
time = M.front().sp;
while(!M.empty() && M.front().sp < time + 3) {
node p = M.front(); M.pop();
if(mp[p.x][p.y] == 'Z') continue;
for(int i = 0; i < 4; i ++) {
int nx = p.x + cx[i], ny = p.y + cy[i];
if(chkH(nx, ny)) continue;
if(mp[nx][ny] == 'M') continue;
if(mp[nx][ny] == 'G') return p.sp / 3 + 1;
mp[nx][ny] = 'M';
M.push(node(nx, ny, p.sp + 1));
}
}
// pt();cout << endl;
time = G.front().sp;
while(!G.empty() && G.front().sp < time + 1) {
node p = G.front(); G.pop();
if(mp[p.x][p.y] == 'Z') continue;
for(int i = 0; i < 4; i ++) {
int nx = p.x + cx[i], ny = p.y + cy[i];
if(chkH(nx, ny)) continue;
if(mp[nx][ny] == 'G') continue;
if(mp[nx][ny] == 'M') return p.sp + 1;
mp[nx][ny] = 'G';
G.push(node(nx, ny, p.sp + 1));
}
}
// pt();cout << endl;
}
return -1;
}
signed main(){
cin >> cas;
while(cas --) {
while(!Z.empty()) Z.pop();
while(!G.empty()) G.pop();
while(!M.empty()) M.pop();
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> str;
for(int j = 1; j <= m; j ++){
mp[i][j] = str[j - 1];
if(str[j - 1] == 'G') G.push(node(i, j, 0));
if(str[j - 1] == 'Z') Z.push(node(i, j, 0));
if(str[j - 1] == 'M') M.push(node(i, j, 0));
}
}
cout << sol() << endl;
}
return 0;
}
Astar
加上估值函数的 BFS A*
估值函数不能大于实际价值就好
估的越好 我们越能从队列里取出 最优的状态 减低复杂度
第K短路
正常跑最短路 如果补终止 那么 这个点 第几次出现 就是第K短路上的路径和
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn = 1000 + 10;
const int maxe = 1e5 + 10;
const int INF = 0x3f3f3f3;
typedef pair<int, int> P;
int n, m, s, t, k;
int head[maxn], cnt;
int nxt[maxe << 1], to[maxe << 1], dis[maxe << 1];
void ade(int a, int b, int v) {
to[++ cnt] = b, dis[cnt] = v;
nxt[cnt] = head[a], head[a] = cnt;
}
int rhead[maxn], rcnt;
int rnxt[maxe << 1], rto[maxe << 1], rdis[maxe << 1];
void rade(int a, int b, int v) {
rto[++ rcnt] = b, rdis[rcnt] = v;
rnxt[rcnt] = rhead[a], rhead[a] = rcnt;
}
int f[maxn];
bool vis[maxn];
void dj(int s, int t) {
memset(f, 0x3f, sizeof f);
f[s] = 0;
priority_queue<P> que;
que.push(P(0, s));
while(!que.empty()) {
P p = que.top(); que.pop();
int u = p.second;
if(vis[u]) continue;
vis[u] = 1;
for(int i = rhead[u]; i; i = rnxt[i]) {
int v = rto[i];
if(f[v] > f[u] + rdis[i]) {
f[v] = f[u] + rdis[i];
que.push(P(-f[v], v));
}
}
}
}
struct node{
int u, f, g;
bool operator < (const node & a) const {
return f + g > a.f + a.g;
}
};
int Astar(int s, int t, int k) {
int counts = 0;
priority_queue<node> que;
if(s == t) k ++;
que.push(node{s, 0, 0});
while(!que.empty()) {
node p = que.top(); que.pop();
int u = p.u;
if(u == t) counts++;
if(counts == k) return p.g;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
que.push(node{v, 0, dis[i] + p.g});
}
}
return -1;
}
signed main() {
cin >> n >> m;
for(int i = 1, a, b, c; i <= m; i ++) {
cin >> a >> b >> c;
ade(a, b, c), rade(b, a, c);
}
cin >> s >> t >> k;
dj(t, s);
// for(int i = 1; i <= n; i ++) cout << f[i] << " " ; cout << endl;
cout << Astar(s, t, k) << endl;
return 0;
}
八数码 问题
其实 这里还可以加上 逆序对优化 排除一些无解的情况
#include <bits/stdc++.h>
using namespace std;
const int maxn = 362880 + 100;
const int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
bool vis[maxn];
const int cx[] = {-1, 1, 0, 0};
const int cy[] = {0, 0, -1, 1};
const char op[] = {'u','d','l','r'};
const int endsta = 0;
char path[maxn];
int pre[maxn];
struct node {
int sta, g, f;
int s[9], loc;
bool operator < (const node& a) const {
return g + f > a.g + a.f;
}
};
int cantor(int *a) {
int x = 0;
for (int i = 0; i < 9; ++i) {
int tmp = 0;
for (int j = i + 1; j < 9; ++j)
if (a[j] < a[i])
tmp++;
x += fac[9 - i - 1] * tmp;
}
return x;
}
int dis_f(int *s) {
int res = 0;
for(int i = 0; i < 9; i ++)
if(s[i] != 9) {
int x = i/3, y = i%3;
int xx = (s[i] - 1)/3, yy = (s[i] - 1)%3;
res += abs(x - xx) + abs(y - yy);
}
return res;
}
priority_queue<node>que;
bool astar(node begins) {
begins.sta = cantor(begins.s);
begins.g = 0, begins.f = dis_f(begins.s);
pre[begins.sta] = -1;
vis[begins.sta] = 1;
que.push(begins);
node tmp,now;
while(!que.empty()) {
node now = que.top();
que.pop();
if(now.sta == endsta) return 1;
int x = now.loc / 3, y = now.loc % 3;
for(int i = 0; i < 4; i ++) {
int nx = x + cx[i];
int ny = y + cy[i];
if(nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
tmp = now;
tmp.s[x * 3 + y] = tmp.s[nx * 3 + ny];
tmp.s[nx * 3 + ny] = 9;
tmp.sta = cantor(tmp.s);
if(vis[tmp.sta]) continue;
vis[tmp.sta] = 1;
tmp.loc = nx * 3 + ny;
tmp.g ++;
tmp.f = dis_f(tmp.s);
pre[tmp.sta] = now.sta;
path[tmp.sta] = op[i];
que.push(tmp);
}
}
return 0;
}
void print(int sta) {
if(pre[sta] == -1) return ;
print(pre[sta]);
printf("%c", path[sta]);
}
int main() {
node begins;
char pt;
for(int i = 0; i < 9; i ++ ) {
scanf(" %c", &pt);
if(pt == 'x') begins.s[i] = 9, begins.loc = i;
else begins.s[i] = pt - '0';
}
if(!astar(begins)) puts("unsolvable");
else print(endsta), puts("");
return 0;
}
IDA*
排书
这个估值函数 我一开始写的不太对了 一直T 跪了 有点难
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 25;
int n;
struct node{
int a[maxn];
int reh(){
int cnt = 0;
if ( a[1] != 1 ) ++cnt;
if ( a[n] != n ) ++cnt;
for ( int i = 1; i < n; ++i )
if ( a[i] + 1 != a[i + 1] ) ++cnt;
return ceil( cnt / 3.0 );
}
bool chk() {
for(int i = 1; i < n; i ++)
if(a[i] + 1 != a[i + 1]) return 0;
return 1;
}
node move(int l, int r, int len) {
node b = *this;
for(int i = len + l; i <= r; i ++) b.a[i - len] = b.a[i];
for(int i = r - len + 1; i <= r; i ++) b.a[i] = a[i + l - r + len - 1];
return b;
}
}ts;
int flag;
void dfs(node x, int h,int limit) {
if(flag || x.reh() + h > limit) return;
if(x.chk()) {flag = 1; return ;}
for(int len = 1; len < n; len ++)
for(int i = 1; i + len - 1 <= n; i ++)
for(int j = i + len; j <= n; j ++)
dfs(x.move(i, j, len), h + 1, limit);
}
int main() {
int t; cin >> t;
while(t --) {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> ts.a[i];
flag = 0;
for(int i = 0; i < 5; i ++) {
dfs(ts, 0, i);
if(flag) {
cout << i << endl;
break;
}
}
if(!flag) cout << "5 or more" << endl;
}
return 0;
}
待续。
京公网安备 11010502036488号