《算法竞赛进阶指南》 0x25 ~ 0x28 代码 + 杂谈

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;
}

待续。

全部评论

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务