程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> AOJ 0121 Seven Puzzle {廣度優先搜索}(*)

AOJ 0121 Seven Puzzle {廣度優先搜索}(*)

編輯:關於C++

原題

這裡寫圖片描述

這裡寫圖片描述

這裡寫圖片描述

題意

題意是有一個輸入,比如:

1 0 2 3 4 5 6 7

擺成如下形狀:

1 0 2 3
4 5 6 7

0表示空格,其他數字可以移動到0的位置。最後需要到如下形狀:

0 1 2 3
4 5 6 7

上面的這種情況是需要移動一步,也就是0和1直接移動就好。

代碼

#include
#include
#include
#include
#include

using namespace std;

int dx[4] = { 1,-1,4,-4 };
mapres;

void solve(void) {
    queueque;
    que.push(01234567);
    while (!que.empty()) {
        string v = que.front();
        que.pop();
        int pos = 0;
        for (int i = 0; i < 8; i++)
            if (v[i] == '0')pos = i;

        for (int i = 0; i < 4; i++) {
            if (0 <= pos + dx[i] && pos + dx[i] < 8 &&
                !(pos == 3 && i == 0) && !(pos == 4 && i == 1)) {
                string u = v;
                swap(u[pos], u[pos + dx[i]]);

                if (res[u] == 0) {
                    que.push(u);
                    res[u] = res[v] + 1;
                }
            }
        }
    }
}

int main(void) {
    int in;
    res[01234567] = 1;
    solve();
    while (true) {
        string s;
        for (int i = 0; i < 8; i++) {
            if (!(cin >> in))return 0;
            s += in + '0';
        }
        cout << res[s] - 1 << endl;
    }
    return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved