(AZ-0121) Seven Puzzle(打表+BFS)

Love The Way You Lie 2022-03-10 04:50 153阅读 0赞

[https://cn.vjudge.net/problem/Aizu-0121][https_cn.vjudge.net_problem_Aizu-0121]

题意:

给定一个8宫格,0表示空位,输入一组8宫格摆放序列,请问最少需要移动几次0,能够得到01234567序列

思路:

打表,把每一种情况移动的顺序存放到一个map中,对01234567进行BFS可以得到各种情况,BFS层数就是当前序列需要移动的次数

注意第三个位置和第四个位置之间无法左右移动

#include <iostream>
    #include <algorithm>
    #include <map>
    #include <string>
    #include <queue>
    using namespace std;
    map<string, int> hsTableMap;   //打表,各种情况回到012345678的
    int smovesStr[4] = { 1,-1,4,-4 };
    string tarStr = "01234567";
    void BFS_TES() {
    	queue<string> tempStr;
    	tempStr.push(tarStr);
    	while (!tempStr.empty()) {
    		string curStr = tempStr.front();
    		tempStr.pop();
    		int oldmove = curStr.find('0');
    		for (int j = 0; j < 4; ++j) {
    			int newMove = curStr.find('0') + smovesStr[j];     //第一行末和第二行处无法移动
    			if (newMove >= 0 && newMove < 8 &&!(oldmove == 3 && j == 0) && !(oldmove == 4 &&  j==1)) {
    				string newStr = curStr;
    				swap(newStr[oldmove], newStr[newMove]);
    				if (hsTableMap[newStr] == 0) {
    					hsTableMap[newStr] = hsTableMap[curStr]+1;
    					tempStr.push(newStr);
    				}
    			}
    		}
    	}
    }
    int main() {
    	string testStr;
    	BFS_TES(); //打表
    	hsTableMap[tarStr] = 0;
    	while (getline(cin, testStr)) {
    		for (auto itr = testStr.begin(); itr != testStr.end();++itr) {
    			if (*itr == ' ') testStr.erase(itr);
    		}
    		cout << hsTableMap[testStr] << endl;
    	}
    	system("PAUSE");
    	return 0;
    }

[https_cn.vjudge.net_problem_Aizu-0121]: https://cn.vjudge.net/problem/Aizu-0121

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 227 Puzzle

1. \include<cstdio> 2. \include<string.h> 3. char ch\[6\]\[6\]; 4. char common\[1010

古城微笑少年丶/ 2024年02月17日 18:44/ 0 赞/ 83 阅读

相关 puzzling(puzzling和puzzled的区别)

puzzlingB)difficultC)terrifyingD? puzzling 使为难的; 费解的; 令人迷惑的, 莫名其妙的 difficult 难的, 困难的

灰太狼/ 2023年09月26日 14:42/ 0 赞/ 144 阅读

相关 puzzles(puzzles in geography课件)

搜狗问问-搜狗旗下最大互动问答社区 ![puzzles][] 搜狗问问-搜狗旗下最大互动问答社区 [puzzles]: https://img2.baidu.c

深藏阁楼爱情的钟/ 2023年09月26日 14:42/ 0 赞/ 68 阅读

相关 puzzle拼图(puzzle拼图9级答案)

3dpuzzle拼图怎么拼装坦克每一个小模块上有编号，字很小，注意看，把中轴立起，从1开始挨个往中间拼，得一半后，把中轴取出来，弄另一半，然后又取中轴，两个合拢后插入中

本是古典何须时尚/ 2023年09月26日 14:42/ 0 赞/ 181 阅读

相关 Egg dropping puzzle

问题：有一个100层高的楼，如果一个鸡蛋从n层掉下来或者n层以上，鸡蛋就会碎掉。已知，现在有两个鸡蛋，找到满足条件的n，使在最坏情况下，丢鸡蛋的次数最少。原题链接可以转到w

Love The Way You Lie/ 2022年08月04日 05:17/ 0 赞/ 186 阅读

相关 Puzzle UVA - 227

Puzzle UVA - 227 题目传送： [https://uva.onlinejudge.org/index.php?option=com\_onlinejud

快来打我*/ 2022年06月10日 10:51/ 0 赞/ 191 阅读

相关 HDU 2612 Find a way ——————BFS + 打表

Find a way Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/O

àì夳堔傛蜴生んèń/ 2022年05月13日 00:38/ 0 赞/ 164 阅读

相关 [java puzzles]puzzle:Oddity

The following method purports to determine whether its sole argument is an odd number.Do

绝地灬酷狼/ 2022年04月16日 01:10/ 0 赞/ 148 阅读

相关 (AZ-0121) Seven Puzzle(打表+BFS)

[https://cn.vjudge.net/problem/Aizu-0121][https_cn.vjudge.net_problem_Aizu-0121] 题意: 给

Love The Way You Lie/ 2022年03月10日 04:50/ 0 赞/ 154 阅读

相关 100-days: thirty-seven

Title: British politics after Theresa May(特蕾莎·梅：英国首相) 　　British politics　英国的政治，英国的政坛，英国

刺骨的言语ヽ痛彻心扉/ 2021年11月09日 08:58/ 0 赞/ 168 阅读