A - 棋盘问题 (POJ 1321)

题意

在一个n*n的棋盘上放置k个棋子,棋子不能同行同列。求方法数。

思路分析

DFS递推。
搜索当前行,每找到一个棋盘位置就递归到下一行搜索。
当前行搜索完毕之后就搜索下一行。

代码

#include<cstdio>
using namespace std;

char map[8][8];
int n, k, cnt, now; // 记录总方案数和当前已经放置的棋子数目。
int vis[8]={0};

void dfs(int cur){
    if(k == now){ cnt++; return; }
    if(cur >= n) return;
    for(int i=0; i<n; i++)
        if(!vis[i] && map[cur][i]=='#'){
            vis[i] = 1;
            now++;
            dfs(cur+1);
            now--;
            vis[i] = 0;
        }
    dfs(cur+1);
}

int main(){
    while(scanf("%d%d", &n, &k) && n != -1 && k != -1){
        for(int i=0; i<n; ++i)
            scanf("%s", map[i]);
        dfs(0);
        printf("%d\n", cnt);
    }
    return 0;
}

B - Dungeon Master (POJ 2251)

题意

三维迷宫题,与迷宫题唯一的区别就是多了向下这一个方向。

思路

BFS+队列。迷宫题正常思路。
用结构体作为队列元素,三维数组存储地图。
找到起点,入队,遍历前后左右上下移动,分别入队。
vis数组进行判重。

代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct node{
    int x, y, z;
    int step;
};
int sx, sy, sz; // 储存起始点坐标
int to[6][3]{1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1}; // 移动方向
int L, R, C; // 长宽高
char map[30][30][30];
int cnt, vis[30][30][30];

int check(int x, int y, int z){ // check it is illegal or not
    if( x<0 || x>=L || y<0 || y>=R || z<0 || z>=C ) return 1;
    if(vis[x][y][z] || map[x][y][z] == '#') return 1;
    return 0;
}

void bfs(){
    queue<node> q;
    node a, b;
    a.x = sx, a.y = sy, a.z = sz;
    a.step = 0;
    vis[a.x][a.y][a.z] = 1;
    q.push(a);
    while(!q.empty()){
        a = q.front(); q.pop();
        if(map[a.x][a.y][a.z] == 'E'){ // 遇到终点结束
            cnt = a.step;
            return;
        }
        for(int i=0; i<6; i++){ // 前后左右上下移动
            b = a;
            b.x += to[i][0];
            b.y += to[i][1];
            b.z += to[i][2];
            if(check(b.x, b.y, b.z)) continue;
            b.step = a.step + 1;
            vis[b.x][b.y][b.z] = 1;
            q.push(b);
        }
    }
    cnt = -1;
}

int main(){
    while(scanf("%d%d%d", &L, &R, &C), L){
        for(int i=0; i<L; i++)
            for(int j=0; j<R; j++)
                scanf("%s", map[i][j]); // input
        for(int i=0; i<L; i++)
            for(int j=0; j<R; j++)
                for(int k=0; k<C; k++)
                    if(map[i][j][k] == 'S'){
                        sx = i; sy = j; sz = k; // find start
                    }
        memset(vis, 0, sizeof(vis)); // initial
        bfs();
        if(cnt == -1) { printf("Trapped!\n"); } // output
        else printf("Escaped in %d minute(s).\n", cnt);
    }
    return 0;
}

C - Catch The Cow (POJ 3278)

题意

农夫去找他的牛。农夫和牛在一直线上,农夫可以对自己的坐标加一减一或者坐标乘二来移动。求最少步数。

思路

BFS+队列。农夫有三种移动,+1-1*2
遍历这三种移动,入队。vis判重。

代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100005;

int n, k;
int Max, dis, Next;
int vis[MAXN], step[MAXN];
int ans;
int min(int n, int m){ return n<m? n:m; }

int bfs(){
    queue<int> q;
    q.push(n);
    step[n] = 0;
    vis[n] = 1;
    while(!q.empty()){
        dis = q.front(); q.pop();
        for(int i=0; i<3; i++){ // 遍历三种移动方式
            if(i == 0) Next = dis-1; // -1
            else if(i == 1) Next = dis*2; // *2
            else Next = dis+1; // +1
            if(!vis[Next] && Next <= MAXN && Next >= 1){
                q.push(Next);
                step[Next] = step[dis]+1;
                vis[Next] = 1;
            }
            if(Next == k) return step[Next];
        }
    }
    return -1;
}

int main(){
    scanf("%d%d", &n, &k); // input
    memset(step, 0x3f, sizeof(step));
    if(n>=k) printf("%d\n", n-k);
    else printf("%d\n", bfs());
    return 0;
}

D - Filptile (POJ 3279)

题意

黑白棋。翻一个自己和四周都换颜色。用0/1表示。
要求最终全为0。

思路

看不出来这是搜索题啊。明明是暴力枚举。
暴力枚举第一行的所有情况。因为一行有n列,所以共有1<<n种可能。所以遍历1<<n次。根据二进制来将每一个格子是0还是1选出(i>>j)&1
根据第一行的情况往下推导出所有的情况,上一行是1的话那下一行就必须要翻。然后检查一下最后一行是否满足条件。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int dirc[5][2]{0, 0, 1, 0, -1, 0, 0, -1, 0, 1};

int m, n;
int map[15][15], filp[15][15], fin[15][15];

int getn(int x, int y){ // 获取x,y点的当前状态
    int block = map[x][y];
    for(int i=0; i<5; i++){
        int bx = x+dirc[i][0];
        int by = y+dirc[i][1];
        if (bx>=0 && bx<m && by>=0 && by<n)
            block += filp[bx][by];
    }
    return block&1;
}

int solve(){
    for(int i=1; i<m; i++)
        for(int j=0; j<n; j++)
            if(getn(i-1, j)) filp[i][j]++;
    for(int i=0; i<n; i++) // 判断最后一行是否符合要求
        if(getn(m-1, i)) return 0;
    int c = 0;
    for(int i=0; i<m; i++)
        for(int j=0; j<n; j++)
            c += filp[i][j]; // 统计步数
    return c;
}

int main(){
    while (scanf("%d%d", &m, &n) != EOF) {
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                scanf("%d", &map[i][j]);
        int cnt = INF;
        for(int i=0; i<(1<<n); i++){
            memset(filp, 0, sizeof(filp));
            for(int j=0; j<n; j++) filp[0][j] = (i>>j)&1; // 二进制法暴力枚举第一行的所有情况。
            int ans = solve(); // 计算第二行及之后的,如果失败返回0,成功返回步数
            if(ans && ans < cnt) {
                cnt = ans;
                memcpy(fin, filp, sizeof(filp));
            }
        }
        // 输出
        if (cnt == INF) printf("IMPOSSIBLE\n");
        else
            for(int i=0; i<m; i++){
                printf("%d", fin[i][0]);
                for(int j=1; j<n; j++) printf(" %d", fin[i][j]);
                printf("\n");
            }
    }
    return 0;
}

E - Find The Multiple (POJ 1426)

题意

找到一个200以内的数的一个乘数,要求这个乘数的每一位都是0或者1。

思路

我的做法是DFS枚举。从1开始向后推,判断是否是n的乘数,如果是就输出,不是就继续。用无符号64位整数可以存到第十九层递归。

代码

#include<cstdio>
using namespace std;

bool find;
void dfs(unsigned __int64 t, int n, int step){
    if (find) return;
    if (!t%n){
        printf("%I64u\n", t);
        find = true;
        return;
    }
    if (step==19) return; // 如果到了第19层就跳出
    dfs(t*10, n, step+1);
    dfs(t*10+1, n, step+1);
    return;
}

int main(){
    int n;
    while(scanf("%d", &n), n){
        find = false;
        dfs(1, n, 0);
    }
    return 0;
}

F -Prime Path (POJ 3126)

题意

给出两个1000-9999之间的素数AB。要求从AB,每次只能换一个数字,并且换完数字之后需要依然是素数。

思路

BFS+队列,最短路。
先打1000-9999素数表。根据素数表BFS找最短路。
先将起点入队。将队首取出,取个十百千四位。通过循环遍历每一位,找到每一位的更换数字,入队。直到找到终点。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
int primeNum[10000];
int T, S, E;
int vis[10000], dis[10000];
int check[4];

void init(){
    memset(primeNum, -1, sizeof(primeNum));
    for(int i=1000; i<9999; i++){ // 打表
        for(int j=2; j<i; j++)
            if(!i%j){ primeNum[i] = 0; break; }
        if(primeNum[i] != 0) { primeNum[i] = 1; }
    }
    scanf("%d",&T);
}

int bfs(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    int a;
    queue<int> q;
    q.push(S);
    vis[S] = 1;
    while (!q.empty()) {
        a = q.front(); q.pop();
        check[0] = a%10; // 个
        check[1] = a%100/10; // 十
        check[2] = a%1000/100; // 百
        check[3] = a/1000; // 千
        for(int i=0; i<4; i++){
            int val = check[i]; // 暂时储存
            for(int j=0; j<10; j++)
                if(j != val){ // 循环寻找相连的节点
                    check[i] = j;
                    int xx = check[0] + check[1]*10 + check[2]*100 + check[3]*1000;
                    if(!vis[xx] && primeNum[xx]){ // 找到了
                        dis[xx] = dis[a]+1;
                        vis[xx] = 1;
                        if(xx == E) return dis[xx]; // 是终点
                        q.push(xx);
                    }
                }
            check[i] = val; // 还原
        }
    }
    return -1;
}

int main(){
    init();
    while(T--){
        scanf("%d%d", &S, &E);
        int steps = bfs();
        if(steps != -1) printf("%d\n", steps);
        else printf("Impossible!\n");
    }
    return 0;
}

G - Shuffle'm Up (POJ 3087)

题意

给两叠牌,洗牌,两叠牌间隔一张相互插入,最下一张是第二叠最下,最上一张是第一叠最上。第二次洗牌取前一半为第一叠,后一半为第二叠。找出是否能到达目标情况,需要洗几次牌。

思路

暴力枚举。模拟洗牌过程,若干次之后肯定会回到初始状态。如果回到初始就跳出。记录洗牌次数。
当时做的时候调了很久的string,果然还是不熟悉C++的问题。
string的下标取用是引用。string只能通过C++的iostream来输入输出。
string在未赋值的时候不具有长度。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

string start, target;
char Begin[205];
int n;// the length of one stack

string Shuffle(string s){
    string temp = start;
    for(int i=0; i<n*2; i++){
        if(~(i&1)) temp[i] = s[n+i/2];
        if(i&1) temp[i] = s[i/2];
    }
    return temp;
}

int solve(){
    string temp;
    int cnt = 1;
    temp = Shuffle(start);
    while (1) {
        if(temp == target) return cnt; // 如果成功,则返回答案
        if(temp == start) return -1; // 如果和起始一样则不可能
        temp = Shuffle(temp); cnt++; // 洗牌
    }
}

int main(){
    int T, time = 0;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        scanf("%s", Begin);
        scanf("%s", Begin+n);
        start = Begin;
        cin >> target;
        printf("%d ", ++time);
        printf("%d\n", solve());
    }
    return 0;
}

H - Pots (POJ 3414)

题意

有两个容器,要达到目标水量。
三种操作,装满,倒空,从一个倒到另一个。
求次数和操作路径。

思路

BFS+数组模拟队列。
容器只有两个,操作也有限,所以能达到的水量肯定是有限的。
用数组模拟队列进行操作。因为水杯容量上限只有100,所以数组开到10000应该足够了。
通过循环来遍历六种情况。六个if会很繁琐,所以用switch来简化。用vis判重。结构体中加上一个pre属性来记录路径。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int A, B, C;
int vis[105][105];
int step; // 最终步数
int flag; // success or not

struct node{
    int k1, k2, op, step, pre; // 当前状态、操作、步数、前一步下标
}q[105*105]; // 模拟队列

int op[105*105]; // 操作在队列中的编号
int lastOp; // 最终操作编号

void bfs(){
    node now, next; int head, tail;
    head = tail = 0;
    q[tail].k1 = q[tail].k2 = q[tail].op = q[tail].step = q[tail].pre = 0;
    tail++;
    memset(vis, 0, sizeof(vis));
    vis[0][0] = 1;

    while(head < tail){
        now = q[head]; head++; // 取队首,出队
        if(now.k1 == C || now.k2 == C){
            flag = 1;
            step = now.step;
            lastOp = head-1;
        }
        for(int i=1; i<=6; i++){
            switch (i) {
                case 1: next.k1 = A; next.k2 = now.k2; break;
                case 2: next.k1 = now.k1; next.k2 = B; break;
                case 3: next.k1 = 0; next.k2 = now.k2; break;
                case 4: next.k1 = now.k1; next.k2 = 0; break;
                case 5:
                    if(now.k1+now.k2 > A){ next.k1 = A; next.k2 = now.k1+now.k2-A; }
                    else { next.k1 = now.k1+now.k2; next.k2 = 0; }
                    break;
                case 6:
                    if(now.k1+now.k2 > B){ next.k2 = B; next.k1 = now.k1+now.k2-B; }
                    else { next.k2 = now.k1+now.k2; next.k1 = 0; }
                    break;
            }
            next.op = i;
            if(!vis[next.k1][next.k2]){
                vis[next.k1][next.k2] = 1;
                next.step = now.step+1;
                next.pre = head-1;
                q[tail].k1 = next.k1; q[tail].k2 = next.k2;
                q[tail].op = next.op; q[tail].step = next.step; q[tail].pre = next.pre;
                tail++;
                if(next.k1 == C || next.k2 == C){
                    flag = 1;
                    step = next.step;
                    lastOp = tail-1;
                    return;
                }
            }
        }
    }
}

int main(){
    while(~scanf("%d%d%d", &A, &B, &C)){
        flag = step = 0;
        bfs();
        if(flag){
            printf("%d\n", step);
            op[step] = lastOp;
            for(int i=step-1; i>0; i--)
                op[i] = q[op[i+1]].pre;
            for(int j=1; j<=step; j++){
                switch (q[op[j]].op) {
                    case 1: printf("FILL(1)\n"); break;
                    case 2: printf("FILL(2)\n"); break;
                    case 3: printf("DROP(1)\n"); break;
                    case 4: printf("DROP(2)\n"); break;
                    case 5: printf("POUR(2,1)\n"); break;
                    case 6: printf("POUR(1,2)\n"); break;
                }
            }
        }
        else printf("impossible\n");
    }
    return 0;
}

L - Oil Deposits (HDU 1241)

题意

找出一共有多少块八方向连通的油田。

思路

DFS连通块。
经典的DFS题目。如果直接暴力递归的话会TLE,所以需要用vis数组判重一下。

总结归纳

刷了十道题,记录有八道题,还有一题连通块DFS和一题迷宫BFS不记。

BFS

BFS主要是用队列来储存下一个状态,循环遍历同一个节点所能够到达的所有情况。所有可以配合方向数组来进行寻找,用结构体来储存节点的状态或者坐标。
适用于寻找最短路。

DFS

DFS主要用递归来向下寻找单条路径的情况。遍历所有路径。