C++演演算法學習之分支限界法的應用

#include<bits/stdc++.h>
using namespace std;
const int M = 31;
int Map[M][M]; // 記錄輸入格子的情況
bool vis[M][M] = { false }; // 標記格子存取情況，預設未存取
int n;
queue <int > q;

void bfs(int x, int y) {  //廣度優先搜尋格子
    int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四個方向
    vis[x][y] = true; //標記格子為存取過
    q.push(x);q.push(y);
    while (!q.empty()) {
        int w = q.front();
        q.pop();
        int e = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {  //遍歷四個方向向外擴充套件一圈
            int now_x = w + dir[i][0];
            int now_y = e + dir[i][1];
            //判斷新格子是否合法
            if (1 <= now_x && now_x <= n && 1 <= now_y && now_y <= n && Map[now_x][now_y] == 0 && !vis[now_x][now_y]) {
                vis[now_x][now_y] = true;//標記格子為存取過
                q.push(now_x);q.push(now_y);
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> Map[i][j];
            if (Map[i][j] == 1)
                vis[i][j] = true;
        }
    }
    for (int i = 1;i <= n;i = i + n - 1) {//從邊緣兩行開始遍歷
        for (int j = 1; j <= n;j++) {
            if (vis[i][j])
                continue;
            bfs(i, j);
        }
    }

    for (int i = 1;i <= n;i = i + n - 1) {//從邊緣兩列開始遍歷
        for (int j = 1;j <= n;j++) {
            if (vis[j][i])
                continue;
            bfs(j, i);
        }
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (vis[i][j])  // 屬於非封閉區域
                cout << Map[i][j] << " ";
            else
                cout << 2 << " ";
        }
        cout << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n, a, b, k[210];
bool f[210] = { false }; // 標記樓層是否存取過，預設沒有

void bfs() {
    queue<pair<int, int> > q; // 定義佇列
    pair<int, int> p, t; // <當前第幾層，當前按了幾次>
    p.first = a; p.second = 0;// 賦初值
    q.push(p);//進入佇列
    while (!q.empty()) {//佇列非空
        p = q.front(); q.pop();
        if (f[p.first]) // 如果樓層存取過
            continue;
        f[p.first] = true; // 標記樓層存取過
        if (p.first == b) { // 達到目標樓層
            cout << p.second << endl;
            return;// 退出搜尋
        }
        if (p.first - k[p.first] > 0) { // 向下按
            t.first = p.first - k[p.first];
            t.second = p.second + 1;
            q.push(t);
        }
        if (p.first + k[p.first] <= n) { // 向上按
            t.first = p.first + k[p.first];
            t.second = p.second + 1;
            q.push(t);
        }
    }
    cout << -1 << endl;
}

int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    bfs(); //廣度優先搜尋答案
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[35][35] = { 0 };  // 記錄方陣初始情況
int n;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; // 上下左右四個方向
int cnt = 0; //記錄某一封閉區域的面積
int cnt_max = 0; // 記錄最大封閉區域的面積
int id = 3; // 搜尋標記
int id_max = id; // 最大封閉區域對應的搜尋標記
void prit() {  // 格式化輸出函數
	int i, j;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			if (a[i][j] == 1) {
				cout << a[i][j] << ' ';
			}
			else if (a[i][j] != id_max) {
				cout << '0' << ' ';
			}
			else {
				cout << '2' << ' ';
			}
		}
		cout << endl;
	}
}

void dfs(int x, int y)//將與其鄰接的0座標改為id
{
	int i;

	if (a[x][y] != 0 || x < 0 || x > n + 1 || y < 0 || y > n + 1) { //檢查是否符合條件
		return;
	}

	a[x][y] = id;
	cnt++;

	for (i = 0; i < 4; i++) { // 搜尋四個方向
		dfs(x + dir[i][0], y + dir[i][1]);
	}
}
int main() {
	int i, j;
	cin >> n;

	for (i = 1; i <= n; i++) { //輸入方陣
		for (j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	//最外圍的0不形成封閉區域
	dfs(0, 0);
	id++;
	for (i = 2; i < n; i++) {//從第二層開始形成封閉區域
		for (j = 2; j < n; j++) {
			cnt = 0;
			dfs(i, j);
			if (cnt > cnt_max) { // 判斷是否為最大封閉區域
				cnt_max = cnt;
				id_max = id;
			}
			id++; // 搜尋標記+1
		}
	}
	prit();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int Map[21][21] = { 0 }; // 記錄區域可通行情況
int m, n;
queue <int > q; 
int num = 1; // 記錄當前是第幾輪搜尋
void bfs(int x, int y, int ex, int ey) {
	int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; // 上下左右四個方向
	q.push(x);q.push(y);
	while (!q.empty()) {
		int s = q.size() / 2; // 當前搜尋輪次有幾個點
		for (int k = 0;k < s;k++) {
			int cur_x = q.front();
			q.pop();
			int cur_y = q.front();
			q.pop();
			for (int i = 0;i < 4;i++) { // 遍歷搜尋四個方向
				int now_x = cur_x + dir[i][0];
				int now_y = cur_y + dir[i][1];
				if (now_x == ex && now_y == ey)  // 判斷是否到終點
					return;

				if (0 <= now_x && now_x < n && 0 <= now_y && now_y < m && Map[now_x][now_y] == 0) { // 判斷當前點是否符合條件
					q.push(now_x);q.push(now_y);
					Map[now_x][now_y] = num; // 標記當前點的搜尋輪次
				}
			}
		}
		num++;
	}
}
int sx, sy, ex, ey;   // 起點終點座標
int main() {
	cin >> m >> n;
	cin >> sx >> sy >> ex >> ey;
	for (int i = 0;i < m;i++)
		for (int j = 0;j < n;j++)
			cin >> Map[i][j];
	bfs(sx, sy, ex, ey);//呼叫bfs函數求解
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			if (i == sx && j == sy) // 起點
				cout << "  a";
			else if (i == ex && j == ey) //終點
				cout << "  b";
			else if (Map[i][j] == num) //與b同層的點
				cout << "  0";
			else {// 其餘點
				if (Map[i][j] < num) 
					printf("%3d", Map[i][j]);
			}

			//cout << "(" << i << "," << j << ")" << endl;
		}
		cout << endl;
	}
	return 0;
}