BFS

从初态S，利用规则生成所有可能的状态，构成下一层节点，检查是否出现目标状态G

若未出现，对该层再次生成、检查，直到出现目标节点

1. 将初始节点添加到队列Q

2. if Q的第一个节点q是目标节点，Then 停止

3. 从Q中删除q，把q的尚未访问的子节点加入Q的末尾

4. if Q为空 Then 失败，Else goto 步骤2

例题：POJ3984

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

int mp[5][5], vis[5][5];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node{
    int x, y;
}; 
node pre[10][10];

void bfs(){
    queue<node> que;
    node str;
    str.x = str.y = 0;
    que.push(str);
    vis[0][0] = 1;
    while (!que.empty()){
        node now = que.front();
        que.pop();
        if (now.x == 4 && now.y == 4) return;
        for (int i = 0; i < 4; i++){
            node next ;
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];
            if (next.x >= 0 && next.x < 5 &&
                next.y >= 0 && next.y < 5 &&
                !mp[next.x][next.y] && !vis[next.x][next.y]){
                vis[next.x][next.y] = 1;
                que.push(next);
                pre[next.x][next.y] = now;
            }
        }
    } 
}

void print(node cur){
    if (cur.x == 0 && cur.y == 0){
        printf("(0, 0)\n");
        return;
    }
    print(pre[cur.x][cur.y]);
    printf("(%d, %d)\n", cur.x, cur.y);
}

int main(){
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) scanf("%d", &mp[i][j]);
    bfs();
    node ed;
    ed.x = ed.y = 4;
    print(ed);
    return 0;
}

例题：POJ1915

#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;

int length, sx, dx, sy, dy;
struct node{
    int x, y, step;
}; 
int visit[310][310];
int po[8][2] = {2, 1, 2, -1, 1, 2, 1, -2, -2, 1, -2, -1, -1, 2, -1, -2};

int check(int x, int y){
    if (x < 0 || x >= length || y < 0 || y >= length) return 1;
    return visit[x][y];
}

void bfs(){
    memset(visit, 0, sizeof(visit));
    node a, b;
    queue<node> Q;
    a.x = sx;
    a.y = sy;
    a.step = 0;
    visit[sx][sy] = 1;
    Q.push(a);
    while (!Q.empty()){
        a = Q.front();
        Q.pop();
        if (a.x == dx && a.y == dy){
            printf("%d\n", a.step);
            return;
        }
        for (int i = 0; i < 8; i++){
            b.x = a.x + po[i][0];
            b.y = a.y + po[i][1];
            if (check(b.x, b.y)) continue;
            b.step = a.step + 1;
            visit[b.x][b.y] = 1;
            Q.push(b);
        }
    } 
}

int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        scanf("%d", &length);
        scanf("%d%d%d%d", &sx, &sy, &dx, &dy);
        bfs();
    }
    return 0;
}

DFS

对每一个可能的分支深入到不能再转移为止，然后回溯到前一步的状态，继续转移到前一步的状态，直到找到最终的解

1. 把起始点放入stack
2. 重复下述3步骤，直到stack为空为止：
3. 从stack中访问栈顶的点
4. 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中
5. 如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。

例题：POJ2386

#include<iostream>
using namespace std;

int N, M;
const int  MAX_N = 103;
char field[MAX_N][MAX_N];

void dfs(int x, int y){
    field[x][y] = '.';
    for (int dx = -1; dx <= 1; dx++){
        for (int dy = -1; dy <= 1; dy++){
            int nx = x + dx, ny = y + dy;
            if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') dfs(nx, ny);
        } 
    }
    return;
}

void solve(){
    int res = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            if (field[i][j] == 'W'){
                dfs(i, j);
                res++;
            }
        }
    }
    cout << res;
}

int main(){
    cin >> N >> M;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> field[i][j];
    solve();
} 

例题：POJ2488

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

const int DN = 8;
const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int N = 27;
bool visit[N][N];
struct Step{
    char x, y;
} path[N];
int p, q, success;

void dfs(int x, int y, int step){
    path[step].y = y + 'A' - 1;
    path[step].x = x + '0';
    if (step == p * q) success = true;
    else {
        for (int i = 0; i < DN && !success; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 < nx && nx <= p && 0 < ny && ny <= q && !visit[nx][ny] && !success){
                visit[nx][ny] = true;
                dfs(nx, ny, step + 1);
                visit[nx][ny] = false;
            }
        }
    }
}

int main(){
    int t;
    scanf("%d", &t);
    for (int k = 1; k <= t; k++){
        scanf("%d%d", &p, &q);
        memset(visit, false, sizeof(visit));
        visit[1][1] = true;
        success = false;
        dfs(1, 1, 1);
        printf("Scenario #%d:\n", k);
        if (success){
            for (int i = 1; i <= p * q; i++) printf("%c%c", path[i].y, path[i].x);
            printf("\n");
        } else printf("impossible\n");
        if (k != t) printf("\n");
    }
    return 0;
}