暴力求解和IDA*(四)

接上一篇的内容
不过在暴力搜索的时候，会有一些复杂的情况
需要数据结构辅助

并查集辅助搜索

HDU3144

算法分析

容易写错的地方
因为这里是尝试连接，并不是一开始就压缩合并并查集

return x == pa[x] ? x : findSet(pa[x]);

这里我们先不需要另pa[x] = findSet(pa[x]);
而是根据我们的尝试，放置'\' or '/'
再Union

//
//  main.cpp
//  HDU3144
//
//  Created by zhangmin chen on 2019/7/28.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 7 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int tar[maxn][maxn];
int cur[maxn][maxn];
char sign[maxn][maxn];

int pa[maxn * maxn];
int n;

void initSet() {
    _for(i, 0, maxn * maxn) pa[i] = i;
}

int findSet(int x) {
    return x == pa[x] ? x : findSet(pa[x]);
}

void init() {
    Set(tar, -1);
    Set(cur, 0);
    Set(sign, 0);
}

bool ok(int p) {
    int x = p / n, y = p % n;
    //
    if(tar[x][y] != -1 && tar[x][y] != cur[x][y]) return false;
    if(x == n - 1 && tar[x + 1][y] != -1 && tar[x + 1][y] != cur[x + 1][y]) return false;
    if(y == n - 1 && tar[x][y + 1] != -1 && tar[x][y + 1] != cur[x][y + 1]) return false;
    if(x == n - 1 && y == n - 1 && tar[x + 1][y + 1] != -1 && tar[x + 1][y + 1] != cur[x + 1][y + 1]) return false;
    
    return true;
}

bool dfs(int p) {
    if(p == n * n) return true;
    
    int x = p / n, y = p % n;
    
    // code: (x + p)
    // try to put (x + p) with '/'
    sign[x][y] = '/';
    int pa1 = findSet(x + p + 1);
    int pa2 = findSet(x + p + 1 + n);
    
    if(pa1 != pa2) {
        int tmp = pa[pa1];
        pa[pa1] = pa2;
        cur[x][y + 1]++;
        cur[x + 1][y]++;
        
        if(ok(p) && dfs(p + 1)) return true;
        
        cur[x + 1][y]--;
        cur[x][y + 1]--;
        pa[pa1] = tmp;
    }
    
    sign[x][y] = '\\';
    pa1 = findSet(x + p);
    pa2 = findSet(x + p + n + 2);
    
    if(pa1 != pa2) {
        int tmp = pa[pa1];
        pa[pa1] = pa2;
        cur[x][y]++;
        cur[x + 1][y + 1]++;
        
        if(ok(p) && dfs(p + 1)) return true;
        
        cur[x + 1][y + 1]--;
        cur[x][y]--;
        pa[pa1] = tmp;
    }
    
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    // int kase;
    // scanf("%d", &kase);
    
    while (scanf("%d", &n) != EOF) {
        //
        init();
        initSet();
        // scanf("%d", &n);
        
        _for(i, 0, n + 1) _for(j, 0, n + 1) {
            char ch;
            cin >> ch;
            
            if(ch == '.') tar[i][j] = -1;
            else tar[i][j] = ch - '0';
        }
        
        /*
        _for(i, 0, n + 1) {
            _for(j, 0, n + 1) printf("% 2d", tar[i][j]);
            printf("\n");
        }
        */
        
        // input finished, then dfs
        
        dfs(0);
        _for(i, 0, n) {
            _for(j, 0, n) cout << sign[i][j];
            printf("\n");
        }
    }
}

表达式划分和搜索

LA5217

省略头文件

const int ch[3] = {'*', '+', '-'};
set<string> output;
char str[maxn];
string res;
int sign[maxn];
int len = 0;
bool ok = 0;

bool cmp(const string& lhs, const string& rhs) {
    return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}

void init() {
    output.clear();
    res.clear();
    Set(sign, 0);
    len = (int)(strlen(str) - 1);
    ok = 0;
}

// is digit [0, len - 1]

inline int cal() {
    // use operator to divide operator into diffrent part
    int val1[maxn], val2[maxn];
    int k1 = 0, k2 = 0;
    int cmd1[maxn], cmd2[maxn];
    int p1 = 0, p2 = 0;
    
    // str -> val1[]
    val1[0] = str[0] - '0';
    _for(i, 0, len - 1) {
        if(sign[i] == 3) {
            // add no cmd
            if(val1[k1] == 0) return 0;
            val1[k1] = val1[k1] * 10 + str[i + 1] - '0';
        }
        else {
            cmd1[p1++] = sign[i];
            val1[++k1] = str[i + 1] - '0';
        }
    }
    // cmd [0, p1 - 1], total length p1
    
    // val1[] -> val2[]
    // connect val1[] through '*'
    // val1[i] cmd[i] val1[i + 1]
    
    val2[0] = val1[0];
    _for(i, 0, p1) {
        if(cmd1[i] == 0) {
            //
            val2[k2] *= val1[i + 1];
        }
        else {
            cmd2[p2++] = cmd1[i];
            val2[++k2] = val1[i + 1];
        }
    }
    
    int ans = val2[0];
    _for(i, 0, p2) {
        if(cmd2[i] == 1) {
            ans += val2[i + 1];
        }
        else {
            ans -= val2[i + 1];
        }
    }
    return ans;
}

void dfs(int d) {
    if(d == len - 1) {
        // calculate
        // [0, len - 1]
        int val = cal();
        //debug(val);
        if(val == 2000) {
            //
            ok = 1;
            res += str[0];
            _for(j, 0, d) {
                if(sign[j] == 3) {
                    // put no operator
                    res += str[j + 1];
                }
                else {
                    //
                    res += ch[sign[j]];
                    res += str[j + 1];
                }
            }
            //cout << "ans" << ans << endl;
            output.insert(res);
            res.clear();
        }
        return;
    }
    
    _for(i, 0, 4) {
        sign[d] = i;
        dfs(d + 1);
    }
}

void solve() {
    if(strcmp(str, "2000=") == 0) {
        printf("  IMPOSSIBLE\n");
        return;
    }
    dfs(0);
    if(ok == 0) printf("  IMPOSSIBLE\n");
    else {
        for(auto& it : output) {
            cout << "  " << it << "=" << endl;
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%s", str) && str[0] != '=') {
        init();
        printf("Problem %d\n", ++kase);
        
        // then we solve the problem
        solve();
    }
}

运算符优先级划分表达式(性能好)

inline int cal() {
    int val1[maxn], val2[maxn];
    int k1 = 0, k2 = 0;

    vector<int> cmd1, cmd2;

    val1[0] = str[0] - '0';
    _for(i, 0, len - 1) {
        if(sign[i] == 3) {
            // add no operator
            if(val1[k1] == 0) return 0;
            val1[k1] = val1[k1] * 10 + str[i + 1] - '0';
        }
        else {
            cmd1.push_back(sign[i]);
            val1[++k1] = str[i + 1] - '0';
        }
    }

    // then calculate *
    val2[0] = val1[0];
    _for(i, 0, cmd1.size()) {
        if(cmd1[i] == 0) val2[k2] *= val1[i + 1];
        else {
            cmd2.push_back(cmd1[i]);
            val2[++k2] = val1[i + 1];
        }
    }

    int ans = val2[0];
    _for(i, 0, cmd2.size()) {
        if(cmd2[i] == 1) ans += val2[i + 1];
        else ans -= val2[i + 1];
    }
    return ans;
}

运算符优先级划分表达式STL(性能差，但是易于实现)

inline int cal() {
    vector<int> val1, val2;
    vector<int> cmd1, cmd2;

    val1.push_back(str[0] - '0');
    _for(i, 0, len - 1) {
        if(sign[i] == 3) {
            // add no operator
            if(val1.back() == 0) return 0;

            int x = val1.back() * 10 + str[i + 1] - '0';
            val1.pop_back();
            val1.push_back(x);
        }
        else {
            cmd1.push_back(sign[i]);
            val1.push_back(str[i + 1] - '0');
        }
    }

    // then calculate *
    val2.push_back(val1[0]);
    _for(i, 0, cmd1.size()) {
        if(cmd1[i] == 0) {
            int x = val2.back() * val1[i + 1];
            val2.pop_back();
            val2.push_back(x);
        }
        else {
            cmd2.push_back(cmd1[i]);
            val2.push_back(val1[i + 1]);
        }
    }

    int ans = val2[0];
    _for(i, 0, cmd2.size()) {
        if(cmd2[i] == 1) ans += val2[i + 1];
        else ans -= val2[i + 1];
    }
    return ans;
}

2D dfs和贪心优化

POJ1011

int used[maxn], len = 0;
int a[maxn], n, cnt;

void init() {
    Set(a, 0);
    len = 0;
}

void initVis() {
    Set(used, 0);
}

bool cmp(int lhs, int rhs) {
    return lhs > rhs;
}

bool dfs(int d, int curlen, int last) {
    //
    if(d > cnt) return true;
    if(curlen == len) return dfs(d + 1, 0, 0);
    
    int fail = 0;
    _for(i, last, n) if(!used[i] && a[i] != fail && curlen + a[i] <= len) {
        used[i] = true;
        if(dfs(d, curlen + a[i], i + 1)) return true;
        fail = a[i];
        used[i] = 0;
        
        if(curlen == 0 || curlen + a[i] == len) return false;
    }
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        
        int sum = 0, maxl = 0;
        _for(i, 0, n) {
            scanf("%d", &a[i]);
            sum += a[i];
            maxl = max(maxl, a[i]);
        }
        
        // scanf finished
        sort(a, a + n, cmp);
        
        for(len = maxl; len <= sum; len++) {
            //
            if(sum % len) continue;
            cnt = sum / len;
            
            initVis();
            if(dfs(1, 0, 0)) break;
        }
        cout << len << endl;
    }
}

矩形枚举(debug经历)

UVA11846

char grid[maxn][maxn];
char ans[maxn][maxn];
int N, K;


class DIR {
public:
    int w, h;
    DIR(int _w = 0, int _h = 0) : w(_w), h(_h) {}
};

void init() {
    Set(grid, '.');
    Set(ans, '.');
}

void dbg() {
    _for(i, 0, N) {
        _for(j, 0, N) printf("%c", grid[i][j]);
        printf("\n");
    }
    printf("\n");
}

void findSZ(const int u, vector<DIR>& dirs) {
    int x = u / N, y = u % N;
    int ey = N;
    // int tmp = 0;
    
    // [x, x + h] and [y, y + w]
    for(int h = 0; x + h < N; h++) for(int w = 0; y + w < ey; w++) {
        // find if valid through [x, x + h]  [y, y + w]
        int nx = x + h, ny = y + w;
        if(ans[nx][ny] != '.') {
            ey = ny;
            break;
        }
        
        int valid = 1, val = inf;
        // find digit in [x, x + h] [y, y + w]
        _rep(i, x, nx) {
            _rep(j, y, ny) {
                if(isdigit(grid[i][j])) {
                    if(val != inf) {
                        valid = false;
                        // tmp = j;
                        break;
                    }
                    else {
                        //
                        val = grid[i][j] - '0';
                        // tmp = j;
                    }
                }
            }
            if(!valid) break;
        }
        // [x, x + h] [y, y + w] find digit num
        
        int sz = (w + 1) * (h + 1);
        // debug(sz);
        // debug(val);
        if(valid && sz == val) {
            dirs.push_back(DIR(w, h));
            // debug(w);
            // debug(h);
            // cout << "====\n";
            // ey = tmp;
            // debug(tmp);
        }
        if(!valid) continue;
    }
}

bool dfs(int u, int id) {
    if(u == N * N) return true;
    if(ans[u / N][u % N] != '.') return dfs(u + 1, id);
    
    vector<DIR> dirs;
    findSZ(u, dirs);
    
    /*
    _for(i, 0, dirs.size()) {
        printf("(%d, %d) => (%d, %d)", u / N, u % N, dirs[i].h, dirs[i].w);
        printf("\n");
    }
    */
    
    int x = u / N, y = u % N;
    _for(k, 0, dirs.size()) {
        int w = dirs[k].w, h = dirs[k].h;
        
        _rep(i, x, x + h) _rep(j, y, y + w) {
            ans[i][j] = 'A' + id;
            // printf("%c", ans[i][j]);
        }
        // printf("finished\n");
        
        if(dfs(u + 1, id + 1)) return true;
        
        _rep(i, x, x + h) _rep(j, y, y + w) {
            ans[i][j] = '.';
        }
    }
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &N, &K) && (N || K)) {
        init();
        _for(i, 0, N) scanf("%s", grid[i]);
        
        //dbg();
        // input finished
        
        dfs(0, 0);
        _for(i, 0, N) {
            _for(j, 0, N) printf("%c", ans[i][j]);
            printf("\n");
        }
    }
}

一些简单题(只需注意中间状态压缩)

其实掌握了框架之后，很多问题都变得简单了
复杂的问题，只需要注意中间状态的压缩
比如当前grid变化，对next grid的影响
用位运算setbit, getbit来压缩模拟状态转移

UVA10384

const int R = 4, C = 6;
const string CH = "WNES";

const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
const int rev[] = {2, 3, 0, 1};

int sx = 0, sy = 0;

int vis[R][C];
int grid[R][C];

vector<char> paths;

void init() {
    Set(grid, 0);
}

void initVis() {
    paths.clear();
    Set(vis, 0);
}

void setbit(int& x, int b, bool flag) {
    if(flag) x |= (1 << b);
    else x &= ~(1 << b);
}
bool getbit(const int x, const int b) {
    return (x & (1 << b)) > 0;
}

bool valid(int x, int y) {
    return 0 <= x && x < R && 0 <= y && y < C;
}

bool isExit(const int x, const int y, vector<char>& paths) {
    int p = grid[x][y];
    if(x == 0 && !getbit(p, 1)) {
        paths.push_back(CH[1]);
        return true;
    }
    
    if(x == R - 1 && !getbit(p, 3)) {
        paths.push_back(CH[3]);
        return true;
    }
    
    if(y == 0 && !getbit(p, 0)) {
        paths.push_back(CH[0]);
        return true;
    }
    
    if(y == C - 1 && !getbit(p, 2)) {
        paths.push_back(CH[2]);
        return true;
    }
    return false;
}

bool dfs(int x, int y, vector<char>& paths, int d, const int maxd) {
    if(isExit(x, y, paths)) return true;
    if(d >= maxd) return false;
    
    int& p = grid[x][y];
    _for(dir, 0, 4) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if(!valid(nx, ny) || vis[nx][ny]) continue;
        
        int& np = grid[nx][ny];
        
        paths.push_back(CH[dir]);
        vis[nx][ny] = 1;
        
        // dfs next position
        if(!getbit(p, dir)) {
            if(dfs(nx, ny, paths, d + 1, maxd)) return true;
        }
        else if(!getbit(np, dir)) {
            // push the wall
            setbit(p, dir, 0); setbit(np, dir, 1); setbit(np, rev[dir], 0);
            // next next position will change because of the pushment
            
            int nnx = nx + dx[dir], nny = ny + dy[dir];
            
            if(valid(nnx, nny)) setbit(grid[nnx][nny], rev[dir], 1);
            if(dfs(nx, ny, paths, d + 1, maxd)) return true;
            if(valid(nnx, nny)) setbit(grid[nnx][nny], rev[dir], 0);
            
            setbit(p, dir, 1); setbit(np, dir, 0); setbit(np, rev[dir], 1);
        }
        
        paths.pop_back();
        vis[nx][ny] = 0;
    }
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    
    while (scanf("%d%d", &sy, &sx) == 2 && (sx || sy)) {
        init();
        _for(i, 0, R) _for(j, 0, C) scanf("%d", &grid[i][j]);
        
        sx--; sy--;
        
        int maxd = 1;
        for(maxd = 1; ; maxd++) {
            initVis();
            vis[sx][sy] = 1;
            if(dfs(sx, sy, paths, 0, maxd)) break;
            vis[sx][sy] = 0;
        }
        
        _for(i, 0, paths.size()) cout << paths[i];
        cout << endl;
    }
}

一些简单题

STL中有些好用，但是不常用的函数，比如copy_backward
在两个vector拼接的时候用的比较多

UVA11882

const int maxr = 15 + 10;
const int maxc = 15 + 10;

int R, C;

int walked[maxr][maxc];
int vis[maxr][maxc];

void initWalk() {
    Set(walked, 0);
}

void initVis() {
    Set(vis, 0);
}

char grid[maxr][maxc];
void init() {
    Set(grid, 0);
}

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};


bool valid(int x, int y) {
    return 0 <= x && x < R && 0 <= y && y < C && isdigit(grid[x][y]);
}

void dbg() {
    _for(i, 0, R) {
        _for(j, 0, C) printf("%c", grid[i][j]);
        printf("\n");
    }
}

class Data {
public:
    vector<char> buf;

    bool operator< (const Data& rhs) const {
        if(buf.size() != rhs.buf.size()) return buf.size() < rhs.buf.size();
        return buf < rhs.buf;
    }

    inline void clear() {
        buf.clear();
    }

    inline int size() const {
        return buf.size();
    }

    Data& operator+= (const char ch) {
        buf.push_back(ch);
        return *this;
    }

    void printAns() {
        _for(i, 0, buf.size()) printf("%c", buf[i]);
        printf("\n");
    }

};

Data cur, ans;

bool cmp(const char a, const char b) {
    return a > b;
}

bool Less(const Data& l1, Data& l2, const Data& rhs) {
    //
    int i = 0;
    for(i = 0; i < l1.buf.size(); i++) {
        int a = l1.buf[i], b = rhs.buf[i];
        if(a < b) return true;
        if(a > b) return false;
    }

    sort(l2.buf.begin(), l2.buf.end(), cmp);
    for(; i < rhs.buf.size(); i++) {
        int a = l2.buf[i - l1.buf.size()], b = rhs.buf[i];
        if(a < b) return true;
        if(a > b) return false;
    }

    return false;
}

void bfs(int x, int y, Data& rs) {
    // get remain routes and data
    initVis();
    queue<int> que;
    que.push(x * maxc + y);
    vis[x][y] = 1;

    while(!que.empty()) {
        int t = que.front();
        que.pop();

        int nx = t / maxc, ny = t % maxc;
        _for(dir, 0, 4) {
            int nnx = nx + dx[dir], nny = ny + dy[dir];
            if(!valid(nnx, nny) || walked[nnx][nny] || vis[nnx][nny]) continue;

            vis[nnx][nny] = 1;
            rs += grid[nnx][nny];
            que.push(nnx * maxc + nny);
        }
    }
}

void dfs(int x, int y, Data& cur, Data& ans) {
    //
    Data rs;
    bfs(x, y, rs);

    if(cur.size() + rs.size() < ans.size()) return;
    if(cur.size() + rs.size() == ans.size() && Less(cur, rs, ans)) return;;

    _for(dir, 0, 4) {
        int nx = x + dx[dir], ny = y + dy[dir];
        if(!valid(nx, ny) || walked[nx][ny]) continue;

        cur += grid[nx][ny];
        walked[nx][ny] = 1;
        dfs(nx, ny, cur, ans);
        cur.buf.pop_back();
        walked[nx][ny] = 0;
    }

    // there is no way to forward
    if(ans < cur) ans = cur;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d%d", &R, &C) == 2 && (R || C)) {
        init();
        initVis();
        initWalk();

        _for(i, 0, R) scanf("%s", grid[i]);
        // dbg();

        ans.clear();
        _for(i, 0, R) _for(j, 0, C) {
            if(!isdigit(grid[i][j])) continue;
            cur.clear();

            // start from grid[i][j]
            cur += grid[i][j];
            walked[i][j] = 1;
            dfs(i, j, cur, ans);
            walked[i][j] = 0;
        }

        // then printf ans
        ans.printAns();
    }
}