emmm…记一些搜索的题目

POJ1321

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

char g[N][N];
bool st[N]; // st数组判断当前列有没有放过
int n, k, res;

void dfs(int u, int cnt)
{
    if (cnt >= k){
        res++;
        return;
    }
    for (int i = u; i < n; i++){
        for (int j = 0; j < n; j++){
            if (g[i][j] == '.' || st[j])    continue; // 判断(i, j)能不能放
            st[j] = 1;
            dfs(i + 1, cnt + 1);
            st[j] = 0;
        }
    }
}

int main()
{
    while (cin >> n >> k, n != -1){
        memset(st, 0, sizeof st);
        for (int i = 0; i < n; i++) cin >> g[i];

        res = 0;
        dfs(0, 0);
        cout << res << endl;
    }

    return 0;
}

POJ 2251

三维空间的走迷宫问题，在三维空间中有上下左右前后6个方向

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 40;

struct node{
    int x, y, z;
};
char g[N][N][N];
int dis[N][N][N], sx, sy, sz, ex, ey, ez;
int z, n, m;
int dx[] = {0, 0, 0, 0, -1, 1};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {1, -1, 0, 0, 0, 0};

void bfs()
{
    memset(dis, -1, sizeof dis);
    queue < node > q;
    q.push({sx, sy, sz});
    dis[sz][sx][sy] = 0;
    while(q.size()){
        node t = q.front();
        q.pop();

        for(int i = 0; i < 6; i ++){
            int nz = t.z + dz[i], nx = t.x + dx[i], ny = t.y + dy[i];
            if(nz < 0 || nz >= z || nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[nz][nx][ny] == '#' || dis[nz][nx][ny] != -1)    continue;

            dis[nz][nx][ny] = dis[t.z][t.x][t.y] + 1;
            q.push({nx, ny, nz});
        }
    }
}

int main()
{
    while(cin >> z >> n >> m, z){
        for(int i = 0; i < z; i ++)
            for(int j = 0; j < n; j ++)
                scanf("%s", g[i][j]);

        for(int i = 0; i < z; i ++){
            for(int j = 0; j < n; j ++){
                for(int k = 0; k < m; k ++){
                    if(g[i][j][k] == 'S')
                        sz = i, sx = j, sy = k;
                    if(g[i][j][k] == 'E')
                        ez = i, ex = j, ey = k;
                }
            }
        }

        bfs();

        if(dis[ez][ex][ey] == -1)
            puts("Trapped!");
        else
        {
            printf("Escaped in %d minute(s).\n", dis[ez][ex][ey]);
        }

    }
    return 0;
}

POJ-3279

首先同一个格子翻转两次就会恢复原状，所以多次翻转是多余的。此外，翻转的格子的集合相同的话，其次序是无关紧要的。 然后就是这个题目可以用状态压缩的思想，将一整行看成是一个二进制数，如果二进制的第 i 位是 1 就代表进行操作

看一个位置的当前状态由什么决定：因为一个位置只能由其四周的操作次数和当前位置I的操作次数决定，当所有可能的操作次数和为奇数时就会改变当前位置的状态，如果当前位置是 1 的话同时操作次数为奇数时，当前位置的状态就会变成0

然后我们可以遍历第一行所有可能的操作次数。此时，能翻转 （1， 1）的只有 (2, 1) 这个位置了，这样当遍历完所有的位置，就能确定所有位置的操作方式了，最后只需要判断最后一行是否还有 1 就能确定当前的操作方式是否成立。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20;

int filp[N][N], tfilp[N][N], ans[N][N], n, m;
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {1, 0, -1, 0, 0};

int get(int x, int y)
{
    int c = filp[x][y];
    for(int i = 0; i < 5; i ++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m)  continue;
        c += tfilp[nx][ny];
    }
    return c % 2;
}

int dfs()
{
    for(int i = 1; i < n; i ++){
        for(int j = 0; j < m; j ++)
            if(get(i - 1, j))
                tfilp[i][j] = 1;
    }

    for(int i = 0; i < m; i ++)
        if(get(n - 1, i))   return -1;
    int num = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            num += tfilp[i][j];
    return num;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> filp[i][j];

    int res = -1;
    for(int i = 0; i < 1 << m; i ++){
        memset(tfilp, 0, sizeof tfilp);
        for(int j = 0; j < m; j ++)
            tfilp[0][m - j - 1] = i >> j & 1;
        int num = dfs();
        if(num != -1 && (res == -1 || num < res)){
            res = num;
            memcpy(ans, tfilp, sizeof tfilp);
        }
    }

    if (res == -1)
        puts("IMPOSSIBLE");
    else{
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (j > 0)  printf(" ");
                printf("%d", ans[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

POJ-1426

dfs 数的每一位，填 1 和 0 两种情况。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100;

int n;

bool dfs(unsigned long long u, int cnt)
{
    if(cnt >= 19)   return false;
    if(u % n == 0){
        cout << u << endl;
        return true;
    }
    if(dfs(u * 10, cnt + 1))    return true;
    if(dfs(u * 10 + 1, cnt + 1))    return true;
    return false;
}

int main()
{
    while(cin >> n, n){
        dfs(1, 0);
    }
    return 0;
}

poj3087

暴力模拟就好了，需要注意的是当前字符串是否出现，如果出现过说明出现了环，需要及时退出

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

const int N = 210;

string s1, s2, s;
int T, n, cas = 1;

int bfs()
{
    queue < string > q;
    map < string , int > dis;
    string st;
    for(int i = 0; i < n; i ++){
        st += s2[i];st += s1[i];
    }
    q.push(st);
    dis[st] = 1;
    while(q.size()){
        string t = q.front();
        q.pop();

        string st1 = t.substr(0, n), st2 = t.substr(n);

        string st;
        for(int i = 0; i < n; i ++){
            st += st2[i];
            st += st1[i];
        }
        if(st == s) return dis[t] + 1;
        if(dis.count(st))   break;
        dis[st] = dis[t] + 1;
        q.push(st);
    }
    return -1;
}

int main()
{
    cin >> T;
    while(T --){
        cin >> n;
        cin >> s1 >> s2 >> s;

        printf("%d %d\n", cas ++, bfs());
    }

    return 0;
}

poj-3414

BFS模拟，一个技巧就是把每次的操作也加上

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 110;

bool st[N][N];
struct node{
    int a, b, dis;
    string res;
    // node (int _a, int _b, string _res, int _dis){
    //     a = _a, b = _b, res = _res, dis = _dis;
    // }
};
int a, b, c;

string bfs()
{
    queue < node > q;
    q.push({0, 0, 0, ""});
    st[0][0] = 1;
    while(q.size()){
        node t = q.front();
        q.pop();

        if(t.a == c || t.b == c){
            cout << t.dis << endl;
            return t.res;
        }
        if(!st[a][t.b]){
            st[a][t.b] = 1;
            q.push({a, t.b, t.dis + 1, t.res + "FILL(1)\n"});
        }
        if(!st[t.a][b]){
            st[t.a][b] = 1;
            q.push({t.a, b, t.dis + 1, t.res + "FILL(2)\n"});
        }
        if(t.a != 0 && !st[0][t.b]){
            st[0][t.b] = 1;
            q.push({0, t.b, t.dis + 1, t.res + "DROP(1)\n"});
        }
        if(t.b != 0 && !st[t.a][0]){
            st[t.a][0] = 1;
            q.push({t.a, 0, t.dis + 1, t.res + "DROP(2)\n"});
        }
        if(t.a != 0){
            int cha = b - t.b;
            if(cha >= t.a){
                if(!st[0][t.a + t.b]){
                    st[0][t.a + t.b] = 1;
                    q.push({0, t.a + t.b, t.dis + 1, t.res + "POUR(1,2)\n"});
                }
            }else{
                if(!st[t.a - cha][b]){
                    st[t.a - cha][b] = 1;
                    q.push({t.a - cha, b, t.dis + 1, t.res + "POUR(1,2)\n"});
                }
            }
        }
        if(t.b != 0){
            int cha = a - t.a;
            if(cha >= t.b){
                if(!st[t.a + t.b][0]){
                    st[t.a + t.b][0] = 1;
                    q.push({t.a + t.b, 0, t.dis + 1, t.res + "POUR(2,1)\n"});
                }
            }else{
                if(!st[a][t.b - cha]){
                    st[a][t.b - cha] = 1;
                    q.push({a, t.b - cha, t.dis + 1, t.res + "POUR(2,1)\n"});
                }
            }
        }
    }
    return "impossible";
}

int main()
{
    cin >> a >> b >> c;
    cout << bfs() << endl;

    return 0;
}

uva-11624

用2个队列分别更新 J 的位置和火的位置，每一次都将队列中的点都遍历一遍

每一次乔先走，每一分钟将所有乔走到的位置都遍历一遍，如果当前点是火走过的位置就不能扩展，然后每次扩展的时候遇到墙或者火都不能扩展

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1010;
typedef pair < int , int > pii;
#define x first
#define y second

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

int bfs()
{
    queue < pii > qa, qb;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            if(g[i][j] == 'J')  
                qa.push({i, j}), st[i][j] = 1;
            if(g[i][j] == 'F')
                g[i][j] == '#', qb.push({i, j});
            } 
        }
    }

    int step = 0;
    while(qa.size()){
        step ++;
        int la = qa.size();
        for(int i = 0; i < la; i ++){
            pii t = qa.front();
            qa.pop();
            // 如果当前位置已经被火扩展到了就不能扩展
            if(g[t.x][t.y] == '#')  continue;
            for(int j = 0; j < 4; j ++){
                int nx = t.x + dx[j], ny = t.y + dy[j];
                if(g[nx][ny] == '#' || st[nx][ny])    continue; // 是墙或者火走过或者自己走过的都不能扩展
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)  return step;
                st[nx][ny] = 1;
                qa.push({nx, ny});
            }
        }
        int lb = qb.size();
        for(int i = 0; i < lb; i ++){
            pii t = qb.front();
            qb.pop();
            for(int j = 0; j < 4; j ++){
                int nx = t.x + dx[j], ny = t.y + dy[j];
                if(g[nx][ny] == '#')    continue;
                if(nx < 0 || nx >= n || ny < 0 || ny >= m)  continue;
                g[nx][ny] = '#';
                qb.push({nx, ny});
            }
        }
    }
    return -1;

}

int main()
{
    cin >> T;
    while(T --){
        memset(st, 0, sizeof st);
        cin >> n >> m;
        for(int i = 0; i < n; i ++) cin >> g[i];

        int num = bfs();

        if(num == -1)
            puts("IMPOSSIBLE");
        else printf("%d\n", num);
    }
    return 0;
}

HDU-2612

bfsＹ到每个KFC的最短时间，bfsM到每个KFC的最短时间，然后遍历每个KFC他俩到达的时间和，找到最小的即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

#define x first
#define y second
typedef pair < int , int > pii;


const int N = 210;

char g[N][N];
int dis1[N][N], dis[N][N], n, m;
int xy, yy, xm, ym;
vector < pii > z;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
bool st[N][N];

void bfs(int x, int y, int dis[][N])
{
    memset(st, 0, sizeof st);
    queue < pii > q;
    q.push({x, y});
    dis[x][y] = 0;
    st[x][y] = 1;

    while(q.size()){
        pii t = q.front();
        q.pop();

        for(int i = 0; i < 4; i ++){
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m)  continue;
            if(g[nx][ny] == '#' || st[nx][ny])  continue;

            st[nx][ny] = 1;
            dis[nx][ny] = dis[t.x][t.y] + 1;
            q.push({nx, ny});
        }
    }
}

int main()
{
    while(cin >> n >> m){
        z.clear();
        memset(dis, 0x3f ,sizeof dis);
        memset(dis1, 0x3f, sizeof dis1);

        for(int i = 0; i < n; i ++) cin >> g[i];

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                if(g[i][j] == '@')  z.push_back({i, j});
                if(g[i][j] == 'Y')  xy = i, yy = j;
                if(g[i][j] == 'M')  xm = i, ym = j;
            }

        bfs(xm, ym, dis);
        bfs(xy, yy, dis1);

        int res = 0x3f3f3f3f;
        for(int i = 0; i < z.size(); i ++){
            res = min(res, dis[z[i].x][z[i].y] + dis1[z[i].x][z[i].y]);
        }
        cout << res * 11 << endl;
    }
    return 0;
}