小进阶
关于memset
它是按照字节对内存块初始化 对于int数组 只能初始化为0或-1 否则不稳定
其它情况还是for来初始化比较妥当
初始化一个0x3f 可以当无穷大使用

因为调用库会有点慢 所以应学会数组模拟队列
快速复习一下
int q[N],hh=0,tt=-1; //hh队头 tt队尾 头在左边便于数组操作
//插入
q[++tt]=x;
//弹出
hh++; 队头指针直接右移一个位置
//判断是否为空
if(hh<=tt) not empty
else empty

bfs中队列的两个性质
1.队列里最多存在两种状态 当取出队头 队尾就会新增x+1
2.单调性 前一段状态为x 后一段状态为x+1

双端队列
由bfs队列中性质 若是走白给的点 那么就把这个点插到队头继续搜
如果是要费用的点 插到队尾 这样就保证了单调性

[洛谷4554] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
int n,m,a,b,x1,y3,x2,y2;
char g[510][510];
int dist[510][510];

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

typedef pair <int,int> PII;
deque <PII> q; //双端队列

int bfs(int x,int y)
{
	q.push_back({x,y});
	dist[x][y]=0;
	while(q.size())
	{
		auto t=q.front();
		q.pop_front();
		char ch=g[t.first][t.second];
		
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			if(a<0 || a>=n || b<0 || b>=m) continue;
			if(dist[a][b]>=0 ) continue;
			
			if(g[a][b]==ch)
			{
				dist[a][b]=dist[t.first][t.second]; //如果有点可以走且符号一样 费用为0 
				q.push_front({a,b}); //这个点插到最前面优先搜 
			}
			
			if(g[a][b]!=ch)
			{
				dist[a][b]=dist[t.first][t.second]+1;
				q.push_back({a,b}); //如果这点要花费 那么就从 
			}
			
			if(a==x2 && b==y2) return dist[x2][y2];
		}
	 } 
	 return -1;
}


int main()
{
	while(cin>>n>>m, n||m )
	{
		//cout<<n<<" "<<m<<endl;
		
		for(int i=0;i<n;i++)
		{
			scanf("%s",g[i]);
		}
		memset(dist,-1,sizeof dist);
		q.clear();
		cin>>x1>>y3>>x2>>y2;
	
		int res=bfs(x1,y3);
		cout<<res<<endl; 
		
		
		
	}
	return 0;
	
}

1.首先 棋盘那么多变化 肯定是存不了的 可以用字符串来表示这个棋盘 这便是一个状态压缩
然后需要一维数组到二维数组 二维数组到一维数组的变化 这是个小技巧
2. map 把一个string 对应一个int 存步骤数
3. count看map里有没有已经出现过下一个要走的点 如果已经出现过就没必要走了
4. 需要回溯 因为是对于一个点四个方向去看

[洛谷1379八数码难题] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
string end1="123804765";

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

unordered_map<string,int> dist;
queue<string> q;

int bfs(string start)
{
	q.push(start);
	dist[start]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		if(t==end1) return dist[t];
		
		int distance=dist[t];
		int a=t.find('0'); //找0的下标 
		int x1=a/3,y1=a%3;//一维下标转二维
		for(int i=0;i<4;i++)
		{
			int x2=x1+dx[i];
			int y2=y1+dy[i];
			if(x2<0 || x2>=3 || y2<0 || y2>=3) continue;
			
			int tmp=x2*3 +y2; //二维下标转一维交换位置 
			swap(t[a],t[tmp]);
			if(!dist.count(t)) //看下一个位置有没有被访问过 
			{
				dist[t]=distance+1;
				q.push(t);
			}
			swap(t[a],t[tmp]); //必须再换回去 
		 } 
	}
	return -1;	
}

int main()
{
	string start;
	cin>>start;
	int res=bfs(start);
	cout<<res<<endl;
	return 0;
}


如果起点和终点的状态已知 那么可以双向bfs
让终点和起点一起入队 同时开始搜 总有一个时刻 起点终点都可以拓展到 此时结束
这样空间占用更少 时间占用也更少

双向bfs维护的是两个队列而不是一个 轮流拓展两个队列 同时用数组或者哈希表记录搜索情况 给从两个方向拓展的节点以不同的标记 当某点被两种标记同时标记时 搜索结束

使用的条件 必须知道初始状态与结束状态
往往涉及如上题的状态压缩

这道之前有 用双向试一试
就是起点初始vs为1 终点为2 如果有个点vs为3则相遇了 return
return 的值需要加1 因为终点初始是0 这一格没有算进去
再次注意输入的是字符

[洛谷] [c++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N]; //存地图
int dist[N][N];
int vs[N][N];
typedef pair<int,int> PII;
queue<PII> s;
int n,x1,y11,x2,y2=0;
PII q[N*N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1}; 

int bfs()
{
	memset(dist,-1,sizeof dist);
	memset(vs,-1,sizeof vs);
	
	dist[x1][y11]=0,dist[x2][y2]=0;
	vs[x1][y11]=1,vs[x2][y2]=2;
	q[0]={x1,y11},q[1]={x2,y2};
	int hh=0,tt=1;
	while(hh<=tt)
	{
		auto t=q[hh++];
		for(int i=0;i<4;i++)
		{
			int a=t.first+dx[i];
			int b=t.second+dy[i];
			if(a<1 || a>n || b<1 || b>n) continue;
			if(g[a][b]!=0) continue; //越界 不是马路
			if(vs[a][b]+vs[t.first][t.second]==3) //说明拓展到了一个点 
			{
				return dist[t.first][t.second]+dist[a][b]+1; //记得加1 因为还有一格 
			}
			if(dist[a][b]>=0) continue; //说明走过了 
			dist[a][b]=dist[t.first][t.second]+1;
			if(vs[a][b]==-1) 
			{
				vs[a][b]=vs[t.first][t.second]; 
			}
			q[++tt]={a,b};	 
		}
		
	}
	return -1;	
}


int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			g[i][j]=c-'0';
		}
	}
	//if(g[1][1]==0) cout<<2<<endl;
	cin>>x1>>y11>>x2>>y2;
	int res=bfs();
	cout<<res;
	return 0;
}

八数码也可以用双向bfs 但是就显得有点复杂了 略