【算法】搜索大法

AcWing 95. 费解的开关

#include 
using namespace std;

const int N = 510;

int n, T;
char g[N][N], back[N][N];
int ans = 0x3f3f3f3f;

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

void change(int x, int y) {
    if(g[x][y] == '0') g[x][y] = '1';
    else g[x][y] = '0';
}

void tune(int x, int y) {
    
    change(x, y);
    
    for(int i=0; i<4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if(a>=0 && a<5 && b>=0 && b<5) {
            change(a, b);
        }
    }
}

int main() {
    
    cin >> T;
    getchar();
    while(T--) {
        
        // cout << 1;
        for(int i=0; i<5; i++) scanf("%s", g[i]);
        
        ans = 0x3f3f3f3f;
        for(int i=0; i < 1<<5; i++) {
            
            memcpy(back, g, sizeof back);
            int step = 0;
            
            for(int j=0; j<5; j++) {
                if(i>>j&1) {
                    tune(0, j);
                    step++;
                }
            }
            
            
            for(int j=0; j<4; j++) {
                for(int k=0; k<5; k++) {
                    if(g[j][k] == '0') {
                        tune(j+1, k);
                        step++;
                    }
                }
            }
            
            bool finish = true;
            for(int j=0; j<5; j++) {
                if(g[4][j] == '0') finish = false;
            }
            
            if(finish) ans = min(ans, step);
            memcpy(g, back, sizeof g);
        }
        
       if(ans <= 6) cout << ans << endl;
       else cout << -1 << endl;
    }

    return 0;
}

AcWing 1209. 带分数

#include 
using namespace std;

const int N = 10;

int n, ans;
int a[N];

int data(int l, int r) {
    
    int res = 0;
    for(int i=l; i<=r; i++) {
        res = res*10 + a[i];
    }
    
    return res;
}

int main() {
    
    cin >> n;
    
    for(int i=0; i<9; i++) a[i] = i + 1;
    
    
    do{
        
        for(int i=0; i<7; i++) {
            for(int j=i+1; j<8; j++) {
                int a = data(0, i);
                int b = data(i+1, j);
                int c = data(j+1, 8);
                // cout << a << " " << b << " " << c << endl;
                
                if(n*c == (a*c + b)) ans++;
                
            }
        }
        
        
    }while(next_permutation(a, a+9));
    
    cout << ans;
    
    
    return 0;
}

AcWing 116. 飞行员兄弟

#include 
using namespace std;

const int N = 5;
typedef pair<int, int> PII;

char g[N][N], back[N][N];

vector<PII> res, ans;

void change(int x, int y) {
    if(g[x][y] == '-') g[x][y] = '+';
    else g[x][y] = '-';
}

void tune(int x, int y) {

    for(int i=0; i<4; i++) change(x, i);
    for(int i=0; i<4; i++) change(i, y);
    
    change(x, y);
}

void dfs(int x, int y) {
    
    if(x == 3 && y == 4) {
        bool flag = true;
        for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                if(g[i][j] == '+') {
                    flag = false;
                    break;
                }
            }
        }
        
        
        if(flag) {
            if(res.size() < ans.size() || ans.empty()) ans = res;
        }
        
        return ;
    }
    
    if(y == 4) x++, y=0;
    dfs(x, y+1);
    
    res.push_back({x, y});
    tune(x, y);
    dfs(x, y+1);
    tune(x, y);
    res.pop_back();
}

int main() {
    
    for(int i=0; i<5; i++) scanf("%s", g[i]);
    
    dfs(0, 0);
    
    printf("%d\n", ans.size());
    for(auto k : ans) {
        int x = k.first + 1, y = k.second + 1;
        printf("%d %d\n", x, y);
    }
    
    
    return 0;
    
}

AcWing 1101. 献给阿尔吉侬的花束

#include 
using namespace std;

const int N = 210;
typedef pair<int, int> PII;
char g[N][N];
int T;
int r, c;
int d[N][N];

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


int bfs(int x, int y) {
    
    queue<PII> q;

    q.push({x, y});
    
    // cout << x << " " << y << endl;
    while(q.size()) {
        auto t = q.front(); q.pop();
        int a = t.first, b = t.second;
        for(int i=0; i<4; i++) {
            int x1 = a + dx[i], y1 = b + dy[i];
            if(x1<=r && x1>=1 && y1<=c && y1>=1 && g[x1][y1] != '#') {
                
                if(!d[x1][y1]) {
                    
                    d[x1][y1] = d[a][b] + 1;
                    
                    // cout << x1 << " " << y1 << " " << d[x1][y1] << endl;
                    if(g[x1][y1] == 'E') return d[x1][y1];
                    q.push({x1, y1});
                    
                }
            }
        }
    }
    
    return 0;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        
        memset(d, 0, sizeof d);
        int x, y;
        
        scanf("%d %d", &r, &c);
        
        for(int i=1; i<=r; i++) {
            scanf("%s", g[i] + 1);
        }
        
    
        for(int i=1; i<=r; i++) {
            for(int j=1; j<=c; j++) {
                if(g[i][j] == 'S') x = i, y = j;
            }
        }

        int t = bfs(x, y);
        
        if(t) cout << t << endl;
        else cout << "oop!" << endl;
        
    }
    
    return 0;
}

AcWing 1240. 完全二叉树的权值

#include 
using namespace std;

const int N = 1e5+10;
int n, a[N];
typedef long long LL;

int bfs() {
    int depth = 0, d = 0;
    int maxv = -0x3f3f3f3f;
    queue<int> q;
    q.push(1);
    while(q.size()) {
        long long s = 0;
        int len = q.size();
        for(int i=0; i<len; i++) {
            int t = q.front(); q.pop();
            s += a[t];
            if((t<<1)<=n) q.push(t<<1);
            if((t<<1|1)<=n) q.push(t<<1|1);
        }
        
        d++;
        
        if(s > maxv) {
            depth = d;
            maxv = s;
        }
    }
    
    return depth;
}

int main() {
    
    cin >> n;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    
    
    cout << bfs();
    
    return 0;
}

AcWing 1096. 地牢大师

#include 
using namespace std;

const int N = 110;
char g[N][N][N];
int l, r, c;
int d[N][N][N];

struct Point{
    int x, y, z;
};

// int dx[6] = {0, 0, 0, 0, 1, -1};
// int dy[6] = {1, -1, 0, 0, 0, 0};
// int dz[6] = {0, 0, 1, -1, 0, 0};

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

int bfs(Point st) {
    queue<Point> q;
    
    q.push(st);
    
    while(q.size()) {
        auto t = q.front(); q.pop();
        int x = t.x, y = t.y, z= t.z;
        for(int i=0; i<6; i++) {
            int a = x + dx[i], b = y + dy[i], h = z + dz[i];
            if(a>=0 && a<l && b>=0 && b<r && h>=0 && h<c && g[a][b][h] != '#' && !d[a][b][h]) {
                d[a][b][h] = d[x][y][z] + 1;
                if(g[a][b][h] == 'E') return d[a][b][h];
                q.push({a, b, h});
            }
        }
    }
    
    return 0;
}

int main() {
    
    while(scanf("%d%d%d", &l, &r, &c), l || r || c) {
        
        memset(d, 0, sizeof d);
        Point st;
        for(int i=0; i<l; i++) {
            for(int j=0; j<r; j++) {
                scanf("%s", g[i][j]);
                for(int k=0; k<c; k++) {
                    char s = g[i][j][k];
                    if(s == 'S') st = {i, j, k};
                }
            }
        }
        
        int t = bfs(st);
        if(t) printf("Escaped in %d minute(s).\n", t);
        else cout << "Trapped!" << endl;
        
        
    }
    
    return 0;
}

AcWing 1233. 全球变暖

#include 
using namespace std;

const int N = 1010;
typedef pair<int, int> PII;

char g[N][N];
bool st[N][N];
int n;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int ans;

void bfs(int x, int y, int &total, int &bound) {
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;
    while(q.size()) {
        auto t = q.front(); q.pop();
        int x = t.first, y = t.second;
        bool flag = false;
        total++;
        for(int i=0; i<4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if(x>=1 && x<=n && y>=1 && y<=n && !st[a][b]) {
                if(g[a][b] == '.') {
                    flag = true;
                } else {
                    st[a][b] = true;
                    q.push({a, b});
                }
            }
        }
        if(flag) bound++;
    }
}

int main() {
    
    cin >> n;
    
    for(int i=1; i<=n; i++) {
        scanf("%s", g[i] + 1);
    }
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            int total = 0, bound = 0;
            if(g[i][j]=='#' && !st[i][j]) {
                bfs(i, j, total, bound);
                if(total == bound) ans++;
            }
        }
    }
    
    cout << ans;
    
    return 0;
}

AcWing 1207. 大臣的旅费

#include 
using namespace std;

const int N = 1e5+10;
typedef pair<int, int> PII;
vector<PII> G[N];
int n, d[N];

void dfs(int u, int fa, int dist) {
    d[u] = dist;
    
    for(auto t : G[u]) {
        int v = t.first, w = t.second;
        if(v != fa) dfs(v, u, dist + w);
    }
    
}

int main() {
    
    scanf("%d",&n);
    
    for(int i=0; i<n; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        G[a].push_back({b, w});
        G[b].push_back({a, w});
    }
    
    
    dfs(1, -1, 0);
    int u = 1;
    for(int i=1; i<=n; i++) {
        if(d[u] < d[i]) u = i;
    }
    
    // cout << u << endl;
    
    dfs(u, -1, 0);
    
    
    for(int i=1; i<=n; i++) {
        if(d[u] < d[i]) u = i;
    }
    
    
    long long res = d[u];
    
    printf("%lld", res*10 + (1+res)*res/2);
    
    return 0;
}