全wa求调
查看原帖
全wa求调
728483
wwwidk1234楼主2024/2/26 12:36

rt,没有输出

在 int pos=tmp.find('0') 后输出 tmp[pos] 全为 0 ,但是在 for 循环里再次输出 tmp[pos] 就不全为 0

#include<bits/stdc++.h>
using namespace std;
map<string,bool> vis;
string s;
int dir[4]={-3,-1,1,3};  //方向  
void bfs()
{
	string nows;  //当前数码 
	int nowc;  //当前次数 
	queue< pair<string,int> > q;
	q.push(make_pair(s,0));
	vis[s]=true;
	while(!q.empty())
	{
		nows=q.front().first;
		nowc=q.front().second;
		string tmp(nows);
		q.pop();
		int pos=tmp.find('0');//寻找0的位置 
		for(int i=0;i<4;i++)
		{
			if(i==1&&(pos==3||pos==6)) continue;
			if(i==2&&(pos==2||pos==5)) continue;
			//检查方块是否被移出 
			if(pos+dir[i]<0||pos+dir[i]>8) continue;
			swap(tmp[pos],tmp[pos+dir[i]]);
			if(!vis[tmp])
			{
				q.push(make_pair(tmp,nowc+1));
//				cout<<tmp<<","<<nowc+1<<endl;
				vis[tmp]=true;
			}
		}
		if(tmp=="123804765")
		{
			cout<<nowc+1;
			return ;
		}
	}
}
int main()
{
//	freopen("puzzle.in","r",stdin);
//	freopen("puzzle.out","w",stdout);
	cin>>s;
	bfs();
	return 0;
}
/*
  string类型:"123405678"
  若要把数字往上,则下标-3
  若要把数字往下,则下标+3
  若要把数字往左,则下标-1
  若要把数字往右,则下标+1 
*/
2024/2/26 12:36
加载中...