kuangbin专题一 - 简单搜索

发表于 2020-04-23 更新于 2021-03-02 阅读次数：

专题链接：https://vjudge.net/article/187

POJ 1321 棋盘问题	POJ 2251 Dungeon Master	POJ 3278 Catch That Cow	POJ 3279 Fliptile
POJ 1426 Find The Multiple	POJ 3126 Prime Path	POJ 3087 Shuffle’m Up	POJ 3414 Pots
FZU 2150 Fire Game	UVA 11624 Fire!	POJ 3984 迷宫问题	HDU 1241 Oil Deposits
HDU 1495 非常可乐	HDU 2612 Find a way

难度系数相对于这些题中最难题目来说，最高难度五颗星

[TOC]

POJ 1321 棋盘问题

分析：二维平面搜索问题
思路：DFS + 回溯
评析：难度系数 ★

AC代码：

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

int sum = 0,n,k;  // sum记录路径个数 n记录棋盘维度 k记录需放的棋子个数 
bool label[10], mat[10][10]; //label标记已经选中的列 mat记录棋盘矩阵 

void dfs(int line, int t) // line行号 t已经放置的棋子个数 
{
    if(t == k) {
        sum++;
        return;
    }
    if(line >= n || n - line < k - t) return;
    dfs(line+1, t);    
    for(int i = 0; i < n; i++){
        if(!label[i] && mat[line][i]){
            label[i] = true;
            dfs(line+1, t+1);
            label[i] = false;
        }
    }
}

int main(int argc, char *argv[])
{
    char x;
    int i,j;
    while(cin >> n >> k){
        sum = 0;
        if(n == -1 && k == -1) break;
        for(i = 0; i < n; i++){
            for(j = 0; j < n; j++){
                cin >> x;
                mat[i][j] = false;
                if(x == '#') mat[i][j] = true;
            }
        }
        memset(label, false, sizeof(label)); 
        dfs(0,0);
        cout << sum << endl;
    }
    return 0;
}

POJ 2251 Dungeon Master

分析：三维空间搜索问题
思路：BFS
评析：难度系数 ★★★

AC代码

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int L,R,C;
int num;

struct point{
    int x; // L
    int y; // R
    int z; // C
};

point bgP,edP;
bool label[30][30][30];

struct node{
    int n;    // number of steps
    int last_op; //0:'up' 1:'down' 2:'left' 3:'right'  -1:'none' 4:'TOP’ 5:'BOTTOM' 
    point pos;
    node():n(0),last_op(-1){
        pos.x = 0;
        pos.y = 0;
        pos.z = 0;    
    }
    node(point p, int tn, int tlast_op){
        pos.x = p.x;
        pos.y = p.y;
        pos.z = p.z;
        n = tn;
        last_op = tlast_op;
    }

};

typedef node* pnode;
typedef vector< vector< vector<char> > > MAZE;



void MYOP(pnode node1, short op, pnode NodeA)
{
    NodeA->n = node1->n+1;
    NodeA->pos.x = node1->pos.x;
    NodeA->pos.y = node1->pos.y;
    NodeA->pos.z = node1->pos.z;
        
    switch(op)
    {
        case 0:{ //up
            NodeA->last_op = 0;
            NodeA->pos.y--; 
            break;    
        };
        case 1:{ //down
            NodeA->last_op = 1;
            NodeA->pos.y++; 
            break;    
        };
        case 2:{ //left
            NodeA->last_op = 2;
            NodeA->pos.z--; 
            break;    
        };
        case 3:{ //right 
            NodeA->last_op = 3;
            NodeA->pos.z++; 
            break;        
        };
        case 4:{ //TOP
            NodeA->last_op = 4;
            NodeA->pos.x++; 
            break;
        };
        case 5:{ //BOTTOM
            NodeA->last_op = 5;
            NodeA->pos.x--; 
            break;
        };
    }

}

bool check(const point &p1)
{
    return p1.x >= 0 && p1.y >= 0 && p1.z >= 0 && p1.x < L && p1.y <R && p1.z < C;
}

void BFS(MAZE &maze)
{
    num = -1;
    queue<pnode> que;
    pnode bgNode = new node(bgP, 0, -1);
    pnode p,tmpN;
    que.push(bgNode);
    label[0][0][0] = true;
    while(!que.empty())
    {
        p = que.front();
        if(p->pos.x == edP.x && p->pos.y == edP.y && p->pos.z == edP.z)
        {
            num = p->n;
            break;
        }
        
        for(short i = 0; i < 6; i++)
        {
            tmpN = new node;
            MYOP(p, i, tmpN);
            if(check(tmpN->pos) && maze[tmpN->pos.x][tmpN->pos.y][tmpN->pos.z] == '.' && !label[tmpN->pos.x][tmpN->pos.y][tmpN->pos.z])
            {
                label[tmpN->pos.x][tmpN->pos.y][tmpN->pos.z] = 1;
                que.push(tmpN);
            }
                
        }
        que.pop();
        delete p;
    }
}



int main(int argc, char *argv[])
{
    int i, j ,k;
    char c;
    while(cin>>L>>R>>C)
    {
        if(L == 0 && R == 0 && C == 0) break;
        MAZE maze;
        
        for(i = 0; i < L; i++)  //lay
        {
            vector< vector<char> > MAT;
            for(j = 0; j < R; j++)
            {
                vector<char> v;
                for(k = 0; k < C; k++)
                {
                    cin >> c; 
                    if(c == 'S'){
                        bgP.x = i;
                        bgP.y = j;
                        bgP.z = k;
                        c = '.';
                    }else if(c == 'E'){
                        edP.x = i;
                        edP.y = j;
                        edP.z = k;
                        c = '.';
                    }
                    v.push_back(c);
                    label[i][j][k] = false;
                }
                MAT.push_back(v);
            }
            maze.push_back(MAT);    
        }
        BFS(maze);
        if(num == -1){
            cout << "Trapped!" << endl;
        }else{
            cout << "Escaped in " << num << " minute(s)." << endl;    
        }
    }    
    return 0;
}

POJ 3278 Catch That Cow

分析：一维线性搜索问题
思路：BFS
评析：难度系数 ★★

AC代码

#include <iostream>
#include <queue>
#include <string.h>

#define MAX_LEN 100100

using namespace std;

int N,K;

struct node{
    int pos;
    int time;
    node():pos(0),time(0){}
    node(int tpos, int ttime):pos(tpos), time(ttime){    }
};

int ops[2] = {-1, 1};

bool visit[MAX_LEN];

void BFS()
{
    queue<node> Que;
    node firstNode(N,0);
    visit[N] = true;
    node tN,tP;
    Que.push(firstNode);
    while(!Que.empty())
    {
        tN = Que.front();
        Que.pop();
        if(tN.pos == K){
            cout << tN.time <<endl;
            return;
        }
        tP.time = tN.time + 1;
        for(int i = 0; i < 2; i++)
        {
            tP.pos = tN.pos + ops[i];
            if(tP.pos >= 0 && tP.pos < MAX_LEN && !visit[tP.pos])
            {
                Que.push(tP);
                visit[tP.pos] = 1;
            }
                
        }
        tP.pos = tN.pos << 1;
        
        if(tP.pos < MAX_LEN && !visit[tP.pos])
        {
            visit[tP.pos] = 1;
            Que.push(tP);
        }
                        
    }    
}
int main(int argc, char *argv[])
{
    cin >> N >> K;
    memset(visit, false, sizeof(visit));
    BFS();
    return 0;
}

POJ 3279 Fliptile

分析：切入点很难想到，编码时无法下手
思路：状态压缩 + 枚举解空间
1. 在所有的解空间中，一旦第一行确定了，后面的几行也全部确定。
  
  先根据第一行的枚举方案，翻转相应的方块，在翻转第二行时，要保证第一行中的1变为0，所以第二行的方案由第一行确定。
2. 枚举第一行的所有方案，就是枚举所有的解空间，为2^M种
3. 状态压缩说明：利用循环，枚举出0~2^M-1之间的数，利用位运算，将对应的二进制0和1赋值到解矩阵的第一行。
4. 并不是每一种方案都有解，当所有行均翻转完毕，检查最后一行是否全部为0，为0，表示该方案是可行解。
评析：难度系数 ★★★★★

AC代码

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

const int MAX_LEN = 16;
int M,N;
bool MAT[MAX_LEN][MAX_LEN];   // COPY from RMAT
bool RMAT[MAX_LEN][MAX_LEN];  // RAW MAT
int FLIP[MAX_LEN][MAX_LEN];
int bestFLIP[MAX_LEN][MAX_LEN];  // optimize choice
unsigned int min_num;
 
void flip(int x, int y)
{
    MAT[x][y] ^= 1;
    if(x - 1 > -1) MAT[x-1][y] ^= 1;
    if(y - 1 > -1) MAT[x][y-1] ^= 1;
    if(x + 1 < M) MAT[x+1][y] ^= 1;
    if(y + 1 < N) MAT[x][y+1] ^= 1;     
} 
void search()
{
    memcpy(MAT, RMAT, sizeof(MAT));
    unsigned int num = 0;
    // flip the first line
    int i,j,k;
    for(i = 0; i < N; i++)
        if(FLIP[0][i]){
        flip(0,i);
        num++;
    }
    // flip the following lines until the last line
    for(i = 1; i < M; i++)
    {
        for(j = 0; j < N; j++)
        {
            if(MAT[i-1][j] == 1){
                flip(i,j);
                FLIP[i][j]++;
                num++; 
                if(num > min_num) return;
            }        
        }
    }
    // check the last line, if each element in the last line is zero, it would be one solution
    bool flag = true;
    for(i = 0; i < N; i++)
        if(MAT[M-1][i]){
            flag = false;
            break;
        }
    if(flag && (num < min_num || min_num < 0))
    {
        min_num = num;
        memcpy(bestFLIP, FLIP, sizeof(FLIP));
    }
        
}
 
int main(int argc, char *argv[])
{
    while(cin >> M >> N)
    {
        memset(MAT, false, MAX_LEN*MAX_LEN);
        for(int i = 0; i < M; i++)
        {
            for(int j = 0; j < N; j++)
                cin >> RMAT[i][j];
        } 
        min_num = -1;
        // generate 2^N situation
        for(unsigned int i = 0; i < (1 << N); i++)
        {
            memset(FLIP, 0, MAX_LEN*MAX_LEN*sizeof(int));
            for(int j = 0; j < N; j++)
            {
                FLIP[0][N-j-1] = (i >> j) & 1;
            }
            search(); 
        }
        if(min_num != -1)
        {
            for(int i = 0; i < M; i++)
            for(int j = 0; j < N; j++)
                printf("%d%c", bestFLIP[i][j], (j == N-1)?'\n':' ');
        }else{
            printf("IMPOSSIBLE\n");
        }
    }
    return 0;
}

POJ 1426 Find The Multiple

分析：不容易想到枚举解空间，需要从输出入手
思路：DFS枚举解空间
1. 枚举解空间，先从1开始，如下：
  1
  2
  3
  4
  5
  1
  / \
  10 11
  / \ / \
  100 101 110 111
2. 可以发现解空间为二叉树结构，可以用数组结构代替
评析：难度系数 ★★★

AC代码

#include <iostream>
#include <vector>
using namespace std;

vector<long long> solution;
int main(int argc, char *argv[])
{
    int n,i;
    while(cin >> n)
    {
        if(n == 0) break;
        solution.push_back(0);
        for(i = 1; ;i++)
        {
            solution.push_back(solution[i/2]*10 + i%2);
            if(solution[i] % n == 0){
                cout << solution[i] << endl;
                break;
            }
        }
        solution.clear();
    }
    return 0;
}

POJ 3126 Prime Path

分析：搜索状态变化主要依据每一位的数字从0-9
思路：BFS

可以将1000-9999之间的所有质数一开始就判断好
评析：难度系数 ★★★

AC代码

#include <iostream>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;

bool prime[9000]; //store prime
bool visit[9000];
int n,t1,t2,t3,t4;

bool isPrime(int t)
{
    int tmp = sqrt(t);
    for(int i = 2; i <= tmp; i++)
    {
        if(t % i == 0)
            return 0;
    }
    return 1;    
}
void init_primeArr()
{
    for(int i = 0; i < 9000; i++)
        if(isPrime(i+1000)) prime[i] = 1;
} 

struct node{
    int x;
    int num;
    node():x(0), num(0){}
    node(int x1, int x2):x(x1), num(x2){}    
};

void BFS()
{
    queue<node> QUE;
    node firstNode(t1,0);
    node N1, N2; 
    QUE.push(firstNode);
    visit[t1-1000] = true;
    int i,j;
    while(!QUE.empty())
    {
        
        N1 = QUE.front();
        QUE.pop();
        if(N1.x == t2){
            cout << N1.num << endl;
            return;
        }
        N2.num = N1.num + 1;
        t4 = 1000;
        for(i = 0; i < 4; i++)
        {
            for(j = !bool(i); j < 10; j++)
            {
                t3 = N1.x % t4 + ((N1.x/(t4*10))*10 + j)*t4;
                if(prime[t3-1000] && !visit[t3-1000]){
                    visit[t3-1000] = 1;
                    N2.x = t3; 
                    QUE.push(N2);
                }        
            }
            t4 /= 10;
        }
    }
    cout << "Impossible" << endl;
}

int main(int argc, char *argv[])
{
    memset(prime, false, sizeof(prime));
    init_primeArr();
    cin >> n;
    while(n--)
    {
        memset(visit, false, sizeof(visit));
        cin >> t1 >> t2;
        BFS(); 
    }
    return 0;
}

POJ 3087 Shuffle’m Up

分析：模拟整个过程
思路：暴力模拟

本人在编写时，为了优化，将两个栈放在一个数组中，利用数组换名，简化过程

结束条件：（1）成功：找到了目标（2）失败：模拟时出现的状态在之前出现过
评析：难度系数 ★★★

AC代码

#include <iostream>
#include <set>
using namespace std;

const int MAX_LEN = 100;
char L1[MAX_LEN*2+1];
char L2[MAX_LEN*2+1];
char *PL1;
char *PL2;
char *PTMP;
int LN;
set<string> MYSET;
int time;
string TARGET;

int shuffle()
{
    string s2(PL1);
    if(s2 == TARGET){
        return time;
    }
    while(1)
    {
        time++;
        int j=0;
        for(int i = 0; i < LN*2; i+=2)
        {
            PL2[i] = PL1[j+LN];
            PL2[i+1] = PL1[j++];
        }
        
        string s(PL2);
        if(s == TARGET){
            return time;
        }else{
            if(MYSET.find(s) != MYSET.end()){
                return -1;
            }
            MYSET.insert(s);
             PTMP = PL1;
             PL1 = PL2;
             PL2 = PTMP;
        }
    }
}

int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> LN;
        cin >> L1;
        cin >> L1+LN;
        cin >> TARGET;
        L1[2*LN] = '\0';
        L2[2*LN] = '\0';
        PL1 = L1; 
        PL2 = L2;
        time = 0;
        cout << i+1 << " " << shuffle() << endl;
        MYSET.clear();
    }
    return 0;
}

POJ 3414 Pots

分析：挺简单的，状态变化的动作已经给出了
思路：BFS

操作过程记录可以利用字符串进行记录。
评析：难度系数 ★★

AC代码

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_LEN = 101;
int A,B,K; //volumn

bool visit[MAX_LEN][MAX_LEN];
string ops[6] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

struct node{
    int a,b;    
    string op; // record the operation
    // 1: fill(1) 2:fill(2) 3:drop(1) 4:drop(2) 5:pour(1,2) 6:pour(2,1)
    node(int x1, int x2, string x3):a(x1), b(x2), op(x3){}
};

void operation(int &a, int &b, int op)
{
    switch(op)
    {
        case 1:{
            a = A;
            break;
        };
        case 2:{
            b = B;
            break;
        };
        case 3:{
            a = 0;
            break;
        };
        case 4:{
            b = 0;
            break;
        };
        case 5:{
            if(B-b >= a)
            {
                b += a;
                a = 0;
            }else{
                a -= B-b;
                b = B;
            }
            break;
        };
        case 6:{
            if(A-a >= b)
            {
                a += b;
                b = 0;
            
            }else{
                b -= A-a;
                a = A;
            }
            break;
        };
    }    
}



void BFS()
{
    queue<node> QUE;
    QUE.push(node(0,0,""));
    visit[0][0] = 1;
    int x,y;
    while(!QUE.empty())
    {
        node STATE = QUE.front();
        QUE.pop();
        if(STATE.a == K || STATE.b == K)
        {
            cout << STATE.op.length() << endl;
            for(int i = 0; i < STATE.op.length(); i++)
                cout << ops[STATE.op[i]-'0'] << endl;
            return; 
        }
        for(int i = 0; i < 6; i++)
        {
            x = STATE.a;
            y = STATE.b;
            operation(x,y,i+1);
            if(!visit[x][y])
            {
                visit[x][y] = 1;
                QUE.push(node(x, y, STATE.op+(char('0'+i))));
            }
        }    
    }
    cout << "impossible" << endl;
}

int main(int argc, char *argv[])
{
    while(cin >> A >> B >> K)
    {
        memset(visit, false, sizeof(visit));
        BFS();
    }    
    return 0;
}

FZU 2150 Fire Game

分析：类似于岛问题
思路：DFS + BFS
1. 先用DFS查看非连通的块的个数，个数大于2，直接输出-1
2. 当块的个数为1或2时，选出两个点作为起点
  
  注：块的个数为1时，起点可以是同一点也可以是不同点
  
  注：块的个数为2时，两个起点必须分布于两个块中
3. 选出起点后，可以用BFS进行搜索
  
  注：BFS搜索时，如果存在时间大于之前找出的最小时间的状态，可以直接结束本次搜索过程，用于加速。
评析：难度系数 ★★★★

AC代码

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

struct point{
    int x;
    int y;
    point(int x1, int x2): x(x1), y(x2){}    
};

struct state{
    int x,y,time;
    state(int x1, int x2, int x3): x(x1), y(x2), time(x3){}
};
const int MAX_LEN = 10;
int N, M, min_step;
char maze[MAX_LEN][MAX_LEN];

// record grass pos
vector<point> grassPos;
bool grassType[MAX_LEN][MAX_LEN];


int blockNum,visitNum;
bool visit[MAX_LEN][MAX_LEN];
void dfs(int x, int y) // to compute num of block
{
    if(x < 0 || y < 0 || x == N || y == M || visit[x][y] || maze[x][y] == '.') return;
    visit[x][y] = 1;
    grassType[x][y] = blockNum;
    visitNum++;
    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
}

void bfs(int num, int x1, int y1, int x2, int y2)
{
    memset(visit, 0, sizeof(visit));
    queue<state> que;
    visit[x1][y1] = 1;
    que.push(state(x1,y1,0));
    if(num == 2){
        visit[x2][y2] = 1;
        que.push(state(x2, y2, 0));
    }
    state staFire(0,0,0);
    while(!que.empty())
    {
        staFire = que.front();
        if(staFire.time > min_step) return;
        que.pop();
        if(staFire.x > 0 && !visit[staFire.x-1][staFire.y] && maze[staFire.x-1][staFire.y] == '#'){
            visit[staFire.x-1][staFire.y] = 1;
            que.push(state(staFire.x-1, staFire.y, staFire.time+1));
        }
        if(staFire.y > 0 && !visit[staFire.x][staFire.y-1] && maze[staFire.x][staFire.y-1] == '#'){
            visit[staFire.x][staFire.y-1] = 1;
            que.push(state(staFire.x, staFire.y-1, staFire.time+1));
        }
        if(staFire.x < N-1 && !visit[staFire.x+1][staFire.y] && maze[staFire.x+1][staFire.y] == '#'){
            visit[staFire.x+1][staFire.y] = 1;
            que.push(state(staFire.x+1, staFire.y, staFire.time+1));
        }
        if(staFire.y < M-1 && !visit[staFire.x][staFire.y+1] && maze[staFire.x][staFire.y+1] == '#'){
            visit[staFire.x][staFire.y+1] = 1;
            que.push(state(staFire.x, staFire.y+1, staFire.time+1));
        }
    }
    if(min_step > staFire.time) min_step = staFire.time;
}

void BFS()
{
    if(blockNum == 0){
        for(int i = 0; i < grassPos.size(); i++)
        {
            for(int j = 0; j < grassPos.size(); j++)
            {
                if(i != j){
                    bfs(2,grassPos[i].x,grassPos[i].y,grassPos[j].x,grassPos[j].y);
                }else{
                    bfs(1,grassPos[i].x,grassPos[i].y,0,0);
                }
            }
            
        }
    }else{
        for(int i = 0; i < grassPos.size(); i++)
        {
            if(grassType[grassPos[i].x][grassPos[i].y] == 0)
            {
                for(int j = 0; j < grassPos.size(); j++)
                {
                    if(grassType[grassPos[j].x][grassPos[j].y])
                    {
                        bfs(2,grassPos[i].x,grassPos[i].y,grassPos[j].x,grassPos[j].y);
                    }
                }
            }    
        }
    }
}

int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> N >> M;
        for(int ii = 0; ii < N; ii++)
            for(int jj = 0; jj < M; jj++)
            {
                cin >> maze[ii][jj];
                if(maze[ii][jj] == '#')
                    grassPos.push_back(point(ii, jj));
            }
        memset(visit, 0, sizeof(visit));
        memset(grassType, 0, sizeof(grassType));
        visitNum = 0;
        blockNum = 0;
        dfs(grassPos[0].x,grassPos[0].y);
        if(visitNum != grassPos.size()){
            blockNum = 1;
            int k;
            for(k = 0; k < grassPos.size(); k++)
            {
                if(!visit[grassPos[k].x][grassPos[k].y]) break;
            }
            dfs(grassPos[k].x, grassPos[k].y);
        }
        if(visitNum == grassPos.size()){
            min_step = 200;
            BFS();
            printf("Case %d: %d\n", i+1, min_step);
        }else{
            printf("Case %d: %d\n", i+1, -1);
        }
        grassPos.clear();
    }
    return 0;
}

UVA 11624 Fire!

分析：两个起点的BFS问题，且起点对象特征不同
思路：BFS
1. 两个起点：人、火
  
  人的状态需要记录时间，火不需要
2. BFS搜索时，处于同一时间的人的状态全部出队时，才能进行一轮火的扩散过程
  
  难点在于这一步
评析：难度系数 ★★★★

AC代码

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_LEN = 1010;

int R,C; 
char maze[MAX_LEN][MAX_LEN]; 
bool visit[MAX_LEN][MAX_LEN];
int JoeX, JoeY;
 
struct statePeo{
    int x,y; //position    
    int time; // time
    statePeo(int p1, int p2, int p3):x(p1), y(p2), time(p3){}
};

struct stateFire{
    int x, y; //position
    int time;
    stateFire(int p1, int p2, int p3):x(p1), y(p2), time(p3){}    
};

vector<stateFire> fireBeginVec;

void BFS()
{
    queue<statePeo> QuePeo;
    queue<stateFire> QueFire;
    for(int i = 0; i < fireBeginVec.size(); i++)
        QueFire.push(fireBeginVec[i]);
    visit[JoeX][JoeY] = 1;
    QuePeo.push(statePeo(JoeX, JoeY, 0));
    int lastTime = 0;
    while(!QuePeo.empty())
    {
        statePeo staPeo = QuePeo.front();
        QuePeo.pop();
        while(!QueFire.empty())
        {
            stateFire staFire = QueFire.front();
            if(staFire.time != staPeo.time) break;
            QueFire.pop();
            if(staFire.x > 1 && maze[staFire.x-1][staFire.y] == '.') {maze[staFire.x-1][staFire.y] = 'F'; QueFire.push(stateFire(staFire.x-1,staFire.y,staFire.time+1));}
            if(staFire.y > 1 && maze[staFire.x][staFire.y-1] == '.') {maze[staFire.x][staFire.y-1] = 'F'; QueFire.push(stateFire(staFire.x,staFire.y-1,staFire.time+1));}
            if(staFire.x < R && maze[staFire.x+1][staFire.y] == '.') {maze[staFire.x+1][staFire.y] = 'F'; QueFire.push(stateFire(staFire.x+1,staFire.y,staFire.time+1));}
            if(staFire.y < C && maze[staFire.x][staFire.y+1] == '.') {maze[staFire.x][staFire.y+1] = 'F'; QueFire.push(stateFire(staFire.x,staFire.y+1,staFire.time+1));}
        }
        if(staPeo.x == 1 || staPeo.y == 1 || staPeo.x  == R || staPeo.y == C){
            cout << staPeo.time + 1 << endl;
            return; 
        }
        if(staPeo.x > 1 && maze[staPeo.x-1][staPeo.y] == '.' && !visit[staPeo.x-1][staPeo.y])
        {
            visit[staPeo.x-1][staPeo.y] = 1;
            QuePeo.push(statePeo(staPeo.x-1, staPeo.y, staPeo.time + 1));
        }
        if(staPeo.y > 1 && maze[staPeo.x][staPeo.y-1] == '.' && !visit[staPeo.x][staPeo.y-1])
        {
            visit[staPeo.x][staPeo.y-1] = 1;
            QuePeo.push(statePeo(staPeo.x, staPeo.y-1, staPeo.time + 1));
        }
        if(staPeo.x < R && maze[staPeo.x+1][staPeo.y] == '.' && !visit[staPeo.x+1][staPeo.y])
        {
            visit[staPeo.x+1][staPeo.y] = 1;
            QuePeo.push(statePeo(staPeo.x+1, staPeo.y, staPeo.time + 1));
        }
        if(staPeo.y < C && maze[staPeo.x][staPeo.y+1] == '.' && !visit[staPeo.x][staPeo.y+1])
        {
            visit[staPeo.x][staPeo.y+1] = 1;
            QuePeo.push(statePeo(staPeo.x, staPeo.y+1, staPeo.time + 1));
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    while(n--)
    {
        cin >> R >> C;
        for(int i = 1; i <= R; i++)
        {
            for(int j = 1; j <= C; j++)
            {
                cin >> maze[i][j];
                if(maze[i][j] == 'J')
                {
                    JoeX = i;
                    JoeY = j;
                }else if(maze[i][j] == 'F')
                    fireBeginVec.push_back(stateFire(i,j,0));
            }
            
        }    
        memset(visit, 0, sizeof(visit));
        BFS();
        fireBeginVec.clear();
    }
    return 0;
}

POJ 3984 迷宫问题

分析：水题，看评论在审查时只有一个测试用例
思路：DFS + 回溯
评析：难度系数 ★

AC代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_LEN = 6;
bool maze[MAX_LEN][MAX_LEN];
bool visit[MAX_LEN][MAX_LEN];
vector<int> vec;
bool flag = false;
void DFS(int x, int y)
{
    if(x == 4 && y == 4){
        flag = 1;
        for(int i = 0; i < vec.size(); i+=2)
            cout << "(" << vec[i] << ", " << vec[i+1] << ")" << endl;
        return;
    }
    if(x < 4 && !visit[x+1][y] && !maze[x+1][y]){
        visit[x+1][y] = 1;
        vec.push_back(x+1);
        vec.push_back(y);
        DFS(x+1, y);
        visit[x+1][y] = 0;
        vec.pop_back();
        vec.pop_back();
    }
    if(flag) return;
    if(y < 4 && !visit[x][y+1] && !maze[x][y+1]){
        visit[x][y+1] = 1;
        vec.push_back(x);
        vec.push_back(y+1);
        DFS(x, y+1);
        vec.pop_back();
        vec.pop_back();
        visit[x][y+1] = 0;    
    }
}

int main(int argc, char *argv[])
{
    flag = false;
    memset(visit, false, sizeof(visit));
    for(int i = 0; i < 5; i++)
        for(int j = 0; j < 5; j++)
            cin >> maze[i][j];
    visit[0][0] = 1;
    vec.push_back(0);
    vec.push_back(0);
    DFS(0, 0);
    return 0;
}

HDU 1241 Oil Deposits

分析：这题貌似可以用并查集来做
思路：DFS
评析：难度系数 ★★

AC代码

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

const int MAX_LEN = 100;
char maze[MAX_LEN][MAX_LEN];
//bool visit[MAX_LEN][MAX_LEN];
int M, N;
int blockNum; 

void dfs(int x, int y)
{
    if(x < 0 || y < 0 || x == M || y == N  || maze[x][y] == '*') return;
    maze[x][y] = '*';
    dfs(x-1, y); dfs(x+1, y); dfs(x, y-1); dfs(x, y+1);
    dfs(x-1, y-1); dfs(x+1, y+1); dfs(x+1, y-1); dfs(x-1, y+1);
}

int main(int argc, char *argv[])
{
    while(cin >> M >> N)
    {
        if(M == 0 && N == 0) break;
        for(int i = 0; i < M; i++)
            for(int j = 0; j < N; j++)
                cin >> maze[i][j];
        blockNum = 0;
        //memset(visit, 0, sizeof(visit));
        for(int i = 0; i < M; i++)
            for(int j = 0; j < N; j++)
            {
                if(maze[i][j] == '@')
                {
                    dfs(i,j);
                    blockNum ++;
                }
            }
        cout << blockNum << endl;
    }
    return 0;
}

HDU 1495 非常可乐

分析：类似于前面的POJ3414 Pots
思路：BFS

最终，只要满足S、N、M三个对象中，两个容器的水量均分，另一容器为空即可。

需要容器没有水时，不要执行将该容器倒水到其他容器（刚开始没注意到这个问题）
评析：难度系数★★

AC代码

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

const int MAX_LEN = 105;
int INPUT[3];

bool visit[MAX_LEN][MAX_LEN][MAX_LEN];
struct state{
    int volumn[3];
    int time;
    state(int x, int y, int z, int m){
        volumn[0] = x;
        volumn[1] = y;
        volumn[2] = z; 
        time = m;
    }    
};

void pour(int from, int to, int &x1, int &x2)
{
    int t1 = INPUT[to] - x2;
    if(t1 >= x1){
        x2 += x1;
        x1 = 0;
    }else{
        x2 = INPUT[to];
        x1 -= t1;
    }
}

void bfs()
{
    queue<state> que;
    visit[INPUT[0]][0][0] = 1;
    que.push(state(INPUT[0], 0, 0, 0));
    int t; 
    while(!que.empty())
    {
        state STA = que.front();
        t = 0;
        for(int i = 0; i < 3; i++)
            if(STA.volumn[i] == INPUT[0]/2) t++; 
        if(t == 2){
            cout << STA.time << endl;
            return;
        }
        que.pop();
        for(int i = 0; i < 3; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                if(i != j)
                {
                    if(STA.volumn[i] == 0) continue;  //注意这里，如果不判断，会多计数一次time 
                    state sta(0,0,0, STA.time+1);
                    sta.volumn[i] = STA.volumn[i];
                    sta.volumn[j] = STA.volumn[j];
                    pour(i, j, sta.volumn[i],sta.volumn[j]);
                    sta.volumn[3-i-j] = STA.volumn[3-i-j];
                    if(!visit[sta.volumn[0]][sta.volumn[1]][sta.volumn[2]])
                    {
                        visit[sta.volumn[0]][sta.volumn[1]][sta.volumn[2]] = 1;
                        que.push(sta);    
                    }    
                }
            }
        }
    }
    cout << "NO" << endl;
}

int main(int argc, char *argv[])
{
    while(cin >> INPUT[0] >> INPUT[1] >> INPUT[2])
    {
        if(INPUT[0] == 0 && INPUT[1] == 0 && INPUT[2] == 0) break;
        if(INPUT[0] % 2 == 0)
        {
            memset(visit, false, sizeof(visit));
            bfs();
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

HDU 2612 Find a way

思路：两次BFS计算两人到每个KFC的最短时间，最后查看到那个KFC时长最短
评析：难度系数★★★

AC代码

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

const int MAX_LEN = 203;
int n,m;
char maze[MAX_LEN][MAX_LEN];
bool visit[MAX_LEN][MAX_LEN];
int KFC[MAX_LEN][MAX_LEN];
int min_time;

struct state{
    int x,y,time;
    state(int x1, int x2, int x3):x(x1), y(x2),time(x3){}
    state():x(0),y(0),time(0){}
};

state Peo[2];

void bfs(int x, int y, int type)
{
    memset(visit, 0, sizeof(visit)); 
    queue<state> que;
    que.push(state(x, y, 0)); 
    visit[x][y] = 1;
    while(!que.empty())
    {
        state STA = que.front();
        if(maze[STA.x][STA.y] == '@'){
            KFC[STA.x][STA.y] += STA.time;
            if(type == 2 && min_time > KFC[STA.x][STA.y]){
                min_time = KFC[STA.x][STA.y];
            }
        }
        que.pop();
        if(STA.x > 0 && maze[STA.x-1][STA.y] != '#' && !visit[STA.x-1][STA.y]){
            visit[STA.x-1][STA.y] = 1;
            que.push(state(STA.x-1, STA.y, STA.time+11));
        }
        if(STA.y > 0 && maze[STA.x][STA.y-1] != '#' && !visit[STA.x][STA.y-1]){
            visit[STA.x][STA.y-1] = 1;
            que.push(state(STA.x, STA.y-1, STA.time+11));
        }
        if(STA.x < n-1 && maze[STA.x+1][STA.y] != '#' && !visit[STA.x+1][STA.y]){
            visit[STA.x+1][STA.y] = 1;
            que.push(state(STA.x+1, STA.y, STA.time+11));
        }
        if(STA.y < m-1 && maze[STA.x][STA.y+1] != '#' && !visit[STA.x][STA.y+1]){
            visit[STA.x][STA.y+1] = 1;
            que.push(state(STA.x, STA.y+1, STA.time+11));
        }
    }
}


int main(int argc, char *argv[])
{
    while(cin >> n >> m)
    {
        min_time = 100000;
        memset(KFC, 0, sizeof(KFC));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin >>  maze[i][j];
                if(maze[i][j] == 'Y')
                {
                    Peo[0].x = i;
                    Peo[0].y = j;
                }else if(maze[i][j] == 'M')
                {
                    Peo[1].x = i;
                    Peo[1].y = j;
                }
            }
        }
        bfs(Peo[0].x, Peo[0].y, 1);
        bfs(Peo[1].x, Peo[1].y, 2);
        cout << min_time << endl;
    }
    return 0;
}