JZTXT

[刷题笔记] Luogu P1379 八数码

发布时间 2023-06-18 15:28:31作者: SXqwq

Problem

Solution

题意非常明确，显然搜索，搜索的时候存储八数码可以用二维或者一维，但是个人感觉用二维更明了一些。

需要注意去重，去重可以用set维护一下已经搜过的八数码，如果手写去重小心MLE

具体实现的时候注意一下细节。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#define N 10010
using namespace std;
set <string> s;
typedef pair<int,int> PAIR;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int startt[5][5] ;
int cnt = 0;
struct Node
{
	int a[5][5];
	int vis;
};
PAIR get_zero(int a[5][5])
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++) if(!a[i][j]) return PAIR(i,j);
	}
}
bool get_ans(int a[5][5])
{
	string chk;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++) chk += (a[i][j] + '0');
	}
	if(chk == "123804765") return true;
	else return false;
}
void bfs()
{
	queue <Node> q;
	Node inp;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++) inp.a[i][j] = startt[i][j];
	}
	inp.vis = 0;
	q.push(inp);
	while(!q.empty())
	{
		Node p = q.front();
		q.pop();
		PAIR zero_add = get_zero(p.a);
		if(get_ans(p.a)) 
		{
			cout<<p.vis<<endl;
			return;
		}
		for(int i=0;i<4;i++)
		{
			int ax = zero_add.first + dx[i]; //找到当前为0的点
			int ay = zero_add.second + dy[i];
			if(ax>=1&&ax<=3&&ay>=1&&ay<=3) //如果不越界
			{
				int t[5][5];
				for(int j=1;j<=3;j++)//获得修改后的map
				{
					for(int k=1;k<=3;k++) t[j][k] = p.a[j][k]; 
				}
				t[zero_add.first][zero_add.second] = t[ax][ay];
				t[ax][ay] = 0;
                string pp;//转换成string与set内比较，去重操作
                for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) pp += (char)t[i][j] +'0';
				if(!s.count(pp))  //如果不重复，即当前map没有被搜过
				{
					Node psh;
                    s.insert(pp);//将当前map加入set
					for(int j=1;j<=3;j++)  //入队
					{
						for(int k=1;k<=3;k++) psh.a[j][k] = t[j][k];
					}
					psh.vis = p.vis + 1; 
					q.push(psh);
				}
			}
		}
	}
}
int main()
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			scanf("%1d",&startt[i][j]);
		}
	}
	bfs();
}

具体实现码量稍大，细节很多，比如将八数码转换成string放入set维护去重，具体存八数码二维数组即可，用string存操作更困难。