发表于 更新于

搜索

flood fill

1097. 池塘计数（poj2386）

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
char g[maxn][maxn];
int ans=0;
int n=0,m=0;
void dfs(int x,int y)
{
    int dx=0,dy=0;
    for(int i=0;i<8;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&g[dx][dy]=='W')
        {
            g[dx][dy]='.';
            dfs(dx,dy);
        }
    }

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='W')
            {
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

1098.城堡计数

dfs

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
// 注意需要dfs返回，不能参数计算不然可能漏方向//

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int g[maxn][maxn],d[maxn][maxn][4],st[maxn][maxn];
int ans=0,room=0;
int n=0,m=0;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&!d[x][y][i]&&!st[dx][dy])
        {

            st[dx][dy]=1;
            cnt+=dfs(dx,dy);
        }
    }
    return cnt;

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
            for(int k=0;k<4;k++)
            {
                if(g[i][j]>>k&1)
                {
                    d[i][j][k]=1;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {

            if(st[i][j])continue;
            st[i][j]=1;
            room++;
            ans=max(ans,dfs(i,j));

        }
    }
    cout<<room<<endl;
    cout<<ans<<endl;
    return 0;
}

bfs

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
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=100086;
int e[INF],a[INF],ne[INF],h[INF],q[INF],idx,n,m; 
int  g[60][60],d[60][60];
typedef pair<int,int >PII;
int space,ans;
int dir[5][3]={{0,-1},{-1,0},{0,1},{1,0}};
void bfs(int x,int y)
{
	queue<PII>q;
	int space1=0;
	d[x][y]=1;
	q.push({x,y});
	int dx=0,dy=0;
	//cout<<x<<","<<y<<endl;
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop();
		int x = t.first, y = t.second ;
		space1++;
		for(int i=0;i<4;i++)
		{//cout<<g[x][y]<<" "<<(g[x][y]>>i&1)<<endl;
		    if(!(g[x][y]>>i&1))
		    {
			    dx=t.first+dir[i][0];
        	    dy=t.second+dir[i][1];
        	    
        	    if(dx>=0&&dx<n&&dy>=0&&dy<m&&!d[dx][dy])
        	    {
        		   // cout<<" "<<dx<<", "<<dy<<endl;
        		    d[dx][dy]=1;
        	    //	pprev[dx][dy]=t;
        		    q.push({dx,dy});
        		    
			    }
		    }
		}
		
	}
	space=max(space,space1);
	return ;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;

	//memset(d,-1,sizeof(d));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>g[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(!d[i][j])
			{
				bfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	cout<<space<<endl;
	return 0;	
}

1106. 山峰和山谷(poi2007)

dfs

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
const int N = 1E3 + 10;
int g[N][N];
int vis[N][N];
int n;
int isp, isv;
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
void dfs(int x, int y)
{
    for(int i = 0; i < 8; i ++ )
    {
        int dx = x + dir[i][0], dy = y + dir[i][1];
        if(!(dx>=0&&dx<n&&dy>=0&&dy<n))  continue;
        if(g[dx][dy] > g[x][y]) isp = 0;
        else if(g[dx][dy] < g[x][y])    isv = 0;
        else if(g[dx][dy] == g[x][y]&&vis[dx][dy] == 0)
        {

            vis[dx][dy] = 1;
            dfs(dx, dy);
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            cin >> g[i][j];
        }

    }
    int peak = 0, valley = 0;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            if(vis[i][j])   continue;
            isp = 1, isv = 1;
            vis[i][j] = 1;
            dfs(i, j);
            if(isp)peak++;
            if(isv)valley++;
//            peak += isp;
//            valley += isv;
        }
    }
    cout << peak << ' ' << valley << endl;
    return 0;
}

bfs

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
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1010;
int d[INF][INF],n,m,ans; 
int g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
int dir[10][3]={{0,0},{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
    {0, 1}, {1, -1}, {1, 0}, {1, 1}};
void bfs(int x,int y,int& isp,int& isv)
{
	int dx=0,dy=0;
	//cout<<x<<","<<y<<endl;
	queue<PII >q;
	q.push({x,y});
	d[x][y]=1;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=1;i<=8;i++)
		{
			dx=t.first+dir[i][0];
        	dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<n))continue;
			
        	if(g[dx][dy]==g[t.first][t.second]&&!d[dx][dy])
        	{
        		//cout<<" "<<dx<<", "<<dy<<endl;
        		//	pprev[dx][dy]=t;
        		q.push({dx,dy});
				d[dx][dy]=1;
			}	
			if(g[dx][dy]>g[t.first][t.second])
			{
				isp=0;
				//d[dx][dy]=1;
				//cout<<" isp"<<dx<<","<<dy<<endl;
			}
			if(g[dx][dy]<g[t.first][t.second])
			{
				isv=0;
				//d[dx][dy]=1;
				//cout<<" isv"<<dx<<","<<dy<<endl;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)
    	for(int j=0;j<n;j++)
    		cin>>g[i][j];
	int peak=0,valley=0;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		if(d[i][j])continue;
    		int isp=1,isv=1;
    		bfs(i,j,isp,isv);
    		if(isp)peak++;
    		if(isv)valley++;
		}
	}    		
    
	cout << peak << " " << valley << endl;
	 
	return 0;	
}

最短路模型

188. 武士风度的牛

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
71
72
73
74
75
76
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
const int N=1010;
int dir[8][2]={{1,2},{2,1},{-1,-2},{-2,-1},{1,-2},{2,-1},{-1,2},{-2,1} };
char g[N][N];
int dis[N][N];
int endx,endy,n,m,ans,sx,sy;
void bfs(int x,int y)
{
	int dx=0,dy=0;
	queue<pii>q;
	q.push({x,y});
	dis[x][y]=1;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int dx=t.first+dir[i][0];
			int dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<m))continue;
			if(g[dx][dy]=='*')continue;
//			cout<<dx<<","<<dy<<endl;
			if(dis[dx][dy]!=0)continue;
			dis[dx][dy]=dis[t.first][t.second]+1;
			q.push({dx,dy});
//			cout<<dis[dx][dy]<<endl;
			if(dx==endx&&dy==endy)
			{
				ans=dis[dx][dy];
				return ;
			}
		}
	}
}

int main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		cin>>g[i][j];
		}
	}
	for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		if(g[i][j]=='K')
    		{
    			sx=i,sy=j;
//    			cout<<sx<<",   "<<sy<<endl;
//    			break;
			}
			else if(g[i][j]=='H')
    		{
    			endx=i;
    			endy=j;
			}
		}
	}
	bfs(sx,sy);
//	cout<<sx<<",   "<<sy<<endl;
	cout<<ans-1<<endl;
    return 0;
}

1100. 抓住那头牛

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,k;
int a[100086];
int b[100086];
int zhuan(int i,int x)
{
	if(i==0)return x-1;
	if(i==1)return x+1;
	if(i==2)return 2*x;
}
int bfs()
{
	queue<int >q;
//	unordered_map<string,int >d;
	q.push(n);
	b[n]=0;
	a[n]=1;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		if(t==k)return b[k];
		for(int i=0;i<3;i++)
		{
			int xx=zhuan(i,t);
			
			if(xx>=0&&xx<=100000&&!a[xx])
			{
				q.push(xx);
				a[xx]=1;
				b[xx]=b[t]+1;
			}
//			cout<<xx<<','<<yy<<endl;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

	cin>>n>>k;
	cout<<bfs()<<endl;
	return 0;	
}

多源bfs

173. 矩阵距离

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
71
72
73
74
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
const int N=1010;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char g[N][N];
int dis[N][N];
int endx,endy,n,m,ans,sx,sy;
void bfs()
{
	int dx=0,dy=0;
	queue<pii>q;
	for(int x=0;x<n;x++)
	{
		for(int y=0;y<m;y++)
		{
			if(g[x][y]=='1')
			{
				q.push({x,y});
				dis[x][y]=1;
			}
			
		}
	}
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int dx=t.first+dir[i][0];
			int dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<m))continue;
			if(g[dx][dy]=='1')continue;
//			cout<<dx<<","<<dy<<endl;
			if(dis[dx][dy]!=0)continue;
			dis[dx][dy]=dis[t.first][t.second]+1;
			q.push({dx,dy});
//			cout<<dis[dx][dy]<<endl;
			
		}
	}
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		cin>>g[i][j];
		}
	}
	
	bfs();
//	cout<<sx<<",   "<<sy<<endl;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
    	{
    		cout<<dis[i][j]-1<<" ";
		}
		cout<<endl;
	}
    return 0;
}

最小步数模型

1107. 魔板

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=110;
int d[INF][INF],n,m; 
int g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
unordered_map< string, int >dist;
unordered_map<string, pair<char, string > >ppre;
string move0(string t)
{
	for(int i=0;i<4;i++)
	{
		swap(t[i],t[7-i]);
	}
	return t;
}
string move1(string t)
{
	for(int i=0;i<3;i++) swap(t[3],t[i]);
    for(int i=4;i<7;i++) swap(t[i],t[i+1]);
    return t;
}
string move2(string t)
{
	swap(t[1],t[2]),swap(t[5],t[6]),swap(t[1],t[5]);
    return t;
}
void bfs(string start,string end)
{
	//cout<<start<<endl;
	//cout<<end<<endl;
	queue<string>q;
	
	q.push(start);
	dist[start]=0;
	
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop();
		if(t==end)break;
		string m[3];
		m[0]=move0(t);
		m[1]=move1(t);
		m[2]=move2(t);
		for(int i=0;i<3;i++)
		{
			string dm=m[i];
			
        	if(dist.count(dm)==0)
        	{
        		dist[dm]=dist[t]+1;
        		ppre[dm]={char(i+'A'),t};
        		if(dm==end)break;
        		q.push(dm);
        	//	cout<<dm<<endl;
			}
			
		}
	}
	cout<<dist[end]<<endl;
	string res;
	if(!dist[end])return;
	while(end!=start)
	{
		res+=ppre[end].first;
		end=ppre[end].second;
	}
	reverse(res.begin(),res.end());
	cout<<res<<endl;
	return ;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x=0;
	string start,end;
	for(int i=0;i<8;i++)
	{
		cin>>x;
		end+=char(x+'0'); 
	}
	for(int i=0;i<8;i++)
	{
		start+=char(i+'1');
	}
	bfs(start,end);
	
	return 0;	
}

双端队列广搜

175. 电路维修

https://www.acwing.com/solution/content/21775/

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=510;
int d[INF][INF],st[INF][INF],n,m; 
char g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
int dir[5][3]={{-1,-1},{-1,1},{1,1},{1,-1}};
int ixy[5][3]={{-1,-1},{-1,0},{0,0},{0,-1}};

int bfs()
{
	
	deque<PII>q;
	memset(d,0x3f,sizeof(d));
	memset(st,0,sizeof(st));
	q.push_front({0,0});
	char ch[5]="\\/\\/";
	
	d[0][0]=0;
	
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop_front();
		int a=t.first,b=t.second;
		if(a==n&&b==m)
		{
			return d[n][m];
		}
		if(st[a][b])continue;
		st[a][b]=1;
		for(int i=0;i<=3;i++)
		{
			int dx=a+dir[i][0];
			int dy=b+dir[i][1];
			if(dx<0||dx>n||dy<0||dy>m)continue;
			int w=0;
			int cx=a+ixy[i][0];
			int cy=b+ixy[i][1];
			if(g[cx][cy]!=ch[i])
			{
				w=1;
			}
			int dw=d[a][b]+w;
        	if(dw<d[dx][dy])
        	{
        		d[dx][dy]=dw;

        	    if(w)q.push_back({dx,dy});
        	    else q.push_front({dx,dy});
			}
		}
	}

	return -1;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=0;
    cin>>t;
    while(t--)
    {
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			cin>>g[i][j];
			}
		}
		if((n+m)&1)cout<<"NO SOLUTION"<<endl;
		else
		{
			cout<<bfs()<<endl;
		}
	}
	
	
	return 0;	
}

双向BFS

190. 字串变换

https://www.acwing.com/solution/content/61327/

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
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair<int,int>pii;
const int N=7;
string a[N],b[N],sa,sb;
unordered_map<string,int> qa,qb;
queue<string> q1,q2;
int n,t;
int extend(queue<string> &q,unordered_map<string,int> &qa,unordered_map<string,int> &qb,string a[],string b[])
{
    string t=q.front();
    q.pop();

    for(int i=0;i<t.size();i++)
    {
        for(int j=0;j<n;j++)
        {
            if(t.substr(i,a[j].size())==a[j])
            {
                string nw=t.substr(0,i)+b[j]+t.substr(i+a[j].size());

                if(qb.count(nw)) return qa[t]+1+qb[nw];
                if(qa.count(nw)) continue;

                q.push(nw);
                qa[nw]=qa[t]+1;
            }
        }
    }
    return 11;
}
int bfs(string sa,string sb)
{
	int t=0;
	if(sa==sb)return 0;
	qa[sa]=0;
	q1.push(sa);
	qb[sb]=0;
	q2.push(sb);
	while(q1.size()&&q2.size())
	{
		if(q1.size()<q2.size())t=extend(q1,qa,qb,a,b);
		else t=extend(q2,qb,qa,b,a);
		if(t<=10 )return t;
	}
	return 11;
	
}

int main()
{
	cin>>sa>>sb;
    if(sa == sb)
	{
	    cout << 0 << '\n';
	    return 0;
	}
	while(cin>>a[n]>>b[n])
	{
		n++;
	}
	int t=bfs(sa,sb);
	if(t>10)
	{
		cout<<"NO ANSWER!"<<endl;
	}
	else
	{
		cout<<t<<endl;
	}
    return 0;
}

lc127. 单词接龙

Astar

178. 第K短路

评论

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair <int,int> PII;
typedef pair <int,PII> PIII;
const int N=1010,INF=0x3f3f3f3f;
int dist[N],cnt[N];
int st[N];
int n,m;
int a,b,c;
int tt,ss,k;
struct edge
{
    int to;
    int length;
    edge(int t,int l):to(t),length(l){}
};
vector<PII>graph[N];
vector<PII>rgraph[N];
void dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[tt] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, tt});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = 0;i<rgraph[ver].size();i++)
        {
            int j = rgraph[ver][i].first;
            int w=rgraph[ver][i].second;
            if (dist[j] > distance + w)
            {
                dist[j] = distance + w;
                heap.push({dist[j], j});
            }
        }
    }
    
}
int astar()
{
	priority_queue <PIII,vector <PIII>,greater <PIII>> heap;
	heap.push({dist[ss],{0,ss}});
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		int ver=t.second.second,distance=t.second.first;
		cnt[ver]++;
		if(cnt[tt]==k)return distance;
		for(int i = 0;i<graph[ver].size();i++)
		{
			int j = graph[ver][i].first;
			int w = graph[ver][i].second;
			if(dist[j]<INF)
			{
				heap.push({distance+w+dist[j],{distance+w,j}});
				
			}
		}
	}
	return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
    	cin>>a>>b>>c;
    	graph[a].push_back({b, c});
        rgraph[b].push_back({a, c});
	}
	cin>>ss>>tt>>k;
	if(ss==tt)k++;
	dij();
	cout<<astar()<<endl;
    return 0;
}

179. 八数码

https://www.acwing.com/solution/content/35528/

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair <int,string> PII;
typedef pair <int,PII> PIII;
const int N=1010,INF=0x3f3f3f3f;
int dist[N],cnt[N];
int st[N];
int n,m;

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
string c,start,x;

int f(string m)
{
	int dt=0;
	for(int i=0;i<9;i++)
	{
		if(m[i]!='x')
		{
			int t=m[i]-'1';
			dt=dt+abs(i/3-t/3)+abs(i%3-t%3);
		}
	}
	return dt;
}
string bfs()
{
	priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆,将元素的估计终点距离从小到大排序
	unordered_map<string,int >d;
	unordered_map<string,pair<string,char>> last;//存储一个元素由哪种状态,经过哪种操作得来,跟前面几题一样
	heap.push({f(start),start});
	char op[]="udlr";
	string end="12345678x";//终点
	d[start]=0;
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		string state=t.second;
		int cnt=d[state];
		if(t.second=="12345678x")break;
		int pos=state.find('x');
		int dx=pos/3,dy=pos%3;
		string init=state;
		for(int i=0;i<4;i++)
		{
			int xx=dx+dir[i][0];
			int yy=dy+dir[i][1];
			if(xx>=0&&xx<3&&yy>=0&&yy<3)
			{
				swap(state[pos],state[xx*3+yy]);
				if(!d.count(state)||d[state]>d[init]+1)
				{
					d[state]=d[init]+1;
					heap.push({f(state)+d[state],state});
					last[state]={init,op[i]};
				}
				swap(state[pos],state[xx*3+yy]);
			}
//			cout<<xx<<','<<yy<<endl;
		}
	}
	string ans;
	while(end!=start)
	{
		ans+=last[end].second;
		end=last[end].first;
	}
	reverse(ans.begin(),ans.end());//将其反转
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	for(int i=0;i<9;i++)
	{
		cin>>c;
		start+=c;
		if(c!="x") x+=c;		
	}
	 int res=0;//统计逆序对的数量
    for(int i=0;i<8;i++)
    	for(int j=i+1;j<8;j++)
    		if(x[i]>x[j]) 
       			res++;

    if(res%2) printf("unsolvable\n");//如果逆序对为奇数,就不可能抵达终点
    else
	cout<<bfs()<<endl;
	return 0;	
}

DFS之连通性模型(flood fill)

1112. 迷宫

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char g[maxn][maxn];
int ans=0,k;
int n=0,ex,ey,sy,sx;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    if(x==ex&&y==ey)return 1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<n&&g[dx][dy]!='#')
        {
            g[dx][dy]='#';
            if(dfs(dx,dy))return 1;
        }
    }
    return 0;

}
int main()
{
	cin>>k;
	while(k--)
	{
		cin>>n;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<n;j++)
	        {
	            cin>>g[i][j];
	        }
	    }
	    cin>>sx>>sy>>ex>>ey;
	    if(g[sx][sy] == '#' || g[ex][ey] == '#')
	    {
	    	cout<<"NO"<<endl;
	    	continue;
		}
	    if(dfs(sx,sy))cout<<"YES"<<endl;
	    else cout<<"NO"<<endl;
	}
    
    return 0;
}

1113. 红与黑

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char g[maxn][maxn];
int st[maxn][maxn];
int ans=0;
int n=0,m=0;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&g[dx][dy]!='#'&&!st[dx][dy])
        {
            st[dx][dy]=1;
            cnt+=dfs(dx,dy);
        }
    }
	return cnt;
}
int main()
{
	while(1)
	{
		cin>>m>>n;
		if(!m&&!n)break;
		memset(st,0,sizeof(st));
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            cin>>g[i][j];
	        }
	    }
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            if(g[i][j]=='@')
	            {
	            	st[i][j]=1;
	                ans=dfs(i,j);
//	                break;
	            }
	        }
	    }
	    cout<<ans<<endl;
	}
    
    return 0;
}

DFS之搜索顺序

1116. 马走日

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int st[maxn][maxn];
int ans=0;
int n=0,m=0,k,sx,sy;
void dfs(int x,int y,int t)
{
    int dx=0,dy=0;
    int cnt=1;
    if(t==n*m)
    {
    	ans++;
    	return;
	}
    for(int i=0;i<8;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&!st[dx][dy])
        {
            st[dx][dy]=1;
            dfs(dx,dy,t+1);
            st[dx][dy]=0;
        }
    }
	
}
int main()
{
	cin>>k;
	while(k--)
	{
		ans=0;
		cin>>n>>m>>sx>>sy;
//		sx++,sy++;
//		if(!m&&!n)break;
		memset(st,0,sizeof(st));
	    st[sx][sy]=1;
	    dfs(sx,sy,1);
	   
	    cout<<ans<<endl;
	}
    
    return 0;
}

1117. 单词接龙

https://www.acwing.com/solution/content/59984/

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
71
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
int g[maxn][maxn];
string word[maxn];
int used[maxn];
int ans=0;
int n=0,m=0,k,sx,sy;
void dfs(string dragon,int last)
{
    //法一：
// 	ans=max((int)dragon.size(),ans);
//	used[last]++;
	for(int i=0;i<n;i++)
	{
		if(g[last][i]&&used[i]<2)
		{
		    ans=max((int)(dragon+word[i].substr(g[last][i])).size(),ans);
			used[i]++;
			
			dfs(dragon + word[i].substr(g[last][i]), i);
			used[i]--;
		}
	}
//	used[last]--;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>word[i];
	}
    char sta;
    cin>>sta;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		string a=word[i],b=word[j];
    		for(int k=1;k<min(a.size(),b.size());k++)
    		{
    			if(a.substr(a.size()-k,k)==b.substr(0,k))
    			{
    				g[i][j]=k;
    				break;
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(word[i][0]==sta)
		{
            //法一这两行不需要
		    ans=max((int)(word[i]).size(),ans);
			used[i]++;
			dfs(word[i],i);
		}
	}
	cout<<ans<<endl;
    return 0;
}

1118. 分成互质组

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,m=0,k,sx,sy;
vector<vector<int> > g;
int check(int c,int x)
{
	for(int i=0;i<g[c].size();i++)
	{
		if(__gcd(g[c][i],x)>1)return 0;
	}
	return 1;
}
void dfs(int u)
{
	if(g.size()>ans)return;
    if(u==n)
    {
    	ans=min(ans,(int)g.size());
    	return;
	}
	for(int i=0;i<g.size();i++)
	{
		if(check(i,a[u]))
		{
			g[i].push_back(a[u]);
			dfs(u+1);
			g[i].pop_back();
		}
	}
	g.push_back({a[u]});
	dfs(u+1);
	g.pop_back();
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	dfs(0);
	cout<<ans<<endl;
    return 0;
}

DFS之剪枝与优化

165. 小猫爬山

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
vector<int>sum;
bool cmp(int a, int b) 
{
    return a > b;
}
void dfs(int u)
{
	if(sum.size()>=ans)return;
    if(u==n)
    {
    	ans=min(ans,(int)sum.size());
    	return;
	}
	for(int i=0;i<sum.size();i++)
	{
		if(sum[i]+a[u]<=w)
		{
// 			g[i].push_back(a[u]);
			sum[i]+=a[u];
			dfs(u+1);
// 			g[i].pop_back();
			sum[i]-=a[u];
		}
	}
// 	g.push_back({a[u]});
	sum.push_back({a[u]});
	dfs(u+1);
// 	g.pop_back();
	sum.pop_back();
}
int main()
{
	cin>>n>>w;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
    //注意排序的剪枝
	sort(a,a+n,cmp);
	dfs(0);
	cout<<ans<<endl;
    return 0;
}

166. 数独

思路
数独一看就可以暴搜，但一看就会超时，所以考虑剪枝。

优化搜索顺序 ✔ ✔
可以优先搜索位置上能填的数最少的方格

排除等效冗余 ✖ ✖
因为整棵搜索树都会搜到，所以不能排除等效冗余
可行性剪枝 ✔ ✔
这一步可以放在枚举能放的位置上进行优化
由于每一行每一列每一个宫格都不能重复，所以我们可以用位运算优化枚举数的过程
最优化剪枝 ✖ ✖
这里我们无需考虑答案最小，只需考虑是否有解

改进
优化搜索顺序，每次优先搜索可选放入数字最少的空白格子，这样它下面搜索时的分支就会少
假设当前搜索到坐标为（x，y）的这个格子

  1. 先解释一下几个数组的含义
    row【i】表示第i行能放的数有哪些（1-9），是二进制表示的，9个位置上，1代表这个数能放，0代表不能放
    col【j】表示第j行能放的数有哪些（1-9），二进制表示同上
    cell【i】【j】—-这里把坐标看成是3*3的，（i，j）就指向了一个唯一的小型九宫格，也是二进制表示这个小型九宫格里能放的数有哪些
    这样我们在（x，y）这个位置上放的数就是满足行，列，小型九宫格都能放的数，取交集
    row[x]&col[y]&cell[x/3][ y/3 ]三者取交集—(x/3,y/3)是小型九宫格的位置

想到位运算优化，三个二进制数进行与运算，最后得到的二进制数中为1的位置，代表这个数能放进（x，y）这个空格子里

  1. 另一个位运算优化：lowbit（）
    lowbit()可以用来计算一个二进制数里面有多少个1
    lowbit举个例子：lowbit（x） x=10001000（二进制） 会返回1000（二进制）
    因为会返回1000，而不会返回我们想要直到的1在第几位，
    所以我们有额外开了数组map【】 1000->8->log2 8就是3,这样1000就会返回map【1000】=3

    map【100】=2

  2. 另外我们还需要看一下最后三者交集的二进制数结果里有多少个1，根据1的数目选择数目较少的先进行搜索，达到优化搜索顺序剪枝的目的：
    用ones【i】记录二进制数i里面有多少个1 (i属于【0,2的9次方-1】)

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
const int N=9;

using namespace std;
typedef pair<int,int> pii;
int  mapp[1<<N],ones[1<<N];
int row[N],col[N],ma[3][3];
string str;
inline void init()
{
	for(int i=0;i<9;i++)
	{
		row[i]=col[i]=(1<<N)-1;
	}
	
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			ma[i][j]=(1<<N)-1;
		}
	}
}
inline int lowbit(int x)
{
	return x&-x;
}
inline int get(int x,int y)
{
	return row[x]&col[y]&ma[x/3][y/3];
}
int dfs(int cnt)
{
	if(!cnt)return 1;
	int minv=10,x=0,y=0;
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(str[i*9+j]=='.')
			{
				int t=ones[get(i,j)];
				if(t<minv)
				{
					minv=t;
					x=i;
					y=j;
				}
			}
			
		}
	}
	for(int i=get(x,y);i;i-=lowbit(i))
	{
		int t=mapp[lowbit(i)];
		row[x]-=(1<<t);
		col[y]-=(1<<t);
		ma[x/3][y/3]-=1<<t;
		str[x*9+y]='1'+t;
		if(dfs(cnt-1))return 1;
		row[x]+=(1<<t);
		col[y]+=(1<<t);
		ma[x/3][y/3]+=1<<t;
		str[x*9+y]='.';
	}
	return 0;
}
int main() 
{
	for(int i=0;i<9;i++)
	{
		mapp[1<<i]=i;
	}
	for(int i=0;i<1<<N;i++)
	{
		int s=0;
		for(int j=i;j;j-=lowbit(j))s++;
		ones[i]=s;
	}
    while(cin>>str)
    {
    	if(str=="end")break;
    	init();
    	int cnt=0;
    	for(int i=0,k=0;i<9;i++)
    	{
    		for(int j=0;j<9;j++,k++)
    		{
    			if(str[k]!='.')
    			{
    				int t=str[k]-'1';
    				row[i]-=1<<t;
    				col[j]-=1<<t;
    				ma[i/3][j/3]-=1<<t;
				}
				else
				{
					cnt++;
				}
			}
		}
		dfs(cnt);
		cout<<str<<endl;
	}
    return 0;
}

167. 木棒

code refer

剪枝策略

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1010;
int len,sum,n,st[N],w[N];
bool cmp(int a, int b) 
{
    return a > b;
}
int dfs(int u,int s,int start)
{
	if(u*len==sum)return 1;
	if(s==len)return dfs(u+1,0,0);//易错
	for(int i=start;i<n;i++)
	{
		if(!st[i]&&s+w[i]<=len)
		{
			st[i]=1;
			if(dfs(u,s+w[i],i+1))return 1;
			st[i]=0;
			if(!s||s+w[i]==len)return 0;
			int j=i;
			while(j<n&&w[j]==w[i])j++;
			i=j-1;
		}
	 } 
	 return 0;
}
int main()
{
	while(cin>>n&&n)
	{
		memset(st,0,sizeof(st));
		sum=0,len=1;
		for(int i=0;i<n;i++)
		{
			cin>>w[i];
			sum+=w[i];
		}
		sort(w,w+n,cmp);
		while(1)
		{
			if(sum%len==0&&dfs(0,0,0))
			{
				cout<<len<<endl;
				break;
			}
			len++;
		}
		
	}
    return 0;
}

168. 生日蛋糕

https://www.acwing.com/solution/content/4187/

image-20230725173137592

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 24, INF = 1e9;
const int maxn=1010;
//char g[maxn][maxn];
int n=0,m=0;
int res=INF,cnt;
int minv[maxn],mins[maxn],hh[maxn],rr[maxn];
void dfs(int u,int v,int s)
{
	if(v+minv[u]>n)return;//可行性
	
	if(s+mins[u]>=res)return;//最优解
	if(s+2*(n-v)/rr[u+1]>=res)return;
//	cout<<n<<" "<<m<<endl;
	if(!u)
	{
		if(v==n)res=s;
		return;
	} 
	for(int r=min(rr[u+1]-1,(int)sqrt((n-v)));r>=u;r--)
	{
		for(int h=min(hh[u+1]-1,(n-v)/r/r);h>=u;h--)
		{
			int t=0;
			//最底层的时候需要加上r*r
			if(u==m)t=r*r;
			rr[u]=r,hh[u]=h;
//			if(u==1)
//			cout<<u<<" "<<r<<" "<<h<<cnt++<<endl;
			dfs(u-1,v+r*r*h,s+2*r*h+t);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		minv[i]=minv[i-1]+i*i*i;
		mins[i]=mins[i-1]+2*i*i;
	}
	//m+1层不存在，作为哨兵，减少边界情况的判断
	rr[m+1]=hh[m+1]=INF;
//	cout<<n<<m<<endl;
	dfs(m,0,0);
	if(res==INF)res=0;
	cout<<res<<endl;
    return 0;
}

迭代加深

170. 加成序列

​ 1

​ 2

4 3

8 6 5 6 5 4

不是同一层不能去重

写法1：

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];

int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	int st[maxn]={0};//定义在本层，只进行本层去重
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
			if(s > n || s <= path[u - 1] || st[s])continue;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		while(!dfs(1,dep))
		{
			dep++;
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

写法2：

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];
int st[maxn]={0};
int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
//			cout<<s<<endl;
			if(s > n || s <= path[u - 1] || st[s])continue;
//			cout<<s<<" u:"<<u<<" "<<path[u-1]<<" "<<depth<<endl;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
			st[s]=0;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		memset(st,0,sizeof(st));
		while(!dfs(1,dep))
		{
			dep++;
			
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

双向DFS

171. 送礼物

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];
int st[maxn]={0};
int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
//			cout<<s<<endl;
			if(s > n || s <= path[u - 1] || st[s])continue;
//			cout<<s<<" u:"<<u<<" "<<path[u-1]<<" "<<depth<<endl;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
			st[s]=0;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		memset(st,0,sizeof(st));
		while(!dfs(1,dep))
		{
			dep++;
			
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

IDA *

180. 排书

https://www.acwing.com/solution/content/161158/

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
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1010,N=31;
//char g[maxn][maxn];
int n;
int q[N],w[5][N];
int f()
{
	int res=0;
	for(int i=0;i+1<n;i++)
	{
		if(q[i+1]!=q[i]+1)
		{
			res++;
		}
	}
	return (res+2)/3;
	
}
bool check()
{
	for(int i=0;i<n;i++)
	{
		if(q[i]!=i+1)
			return false;
	}
	return true;
}
int dfs(int dep,int maxdep)
{
	if(dep+f()>maxdep)return 0;
	if(check())return 1;
	for(int l=0;l<n;l++)
	{
		for(int r=l;r<n;r++)
		{
			for(int k=r+1;k<n;k++)
			{
				memcpy(w[dep],q,sizeof(q));
				int x=0,y=0;
				for(x=r+1,y=l;x<=k;x++,y++)q[y]=w[dep][x];
				for(x=l;x<=r;x++,y++)q[y]=w[dep][x];
				if(dfs(dep+1,maxdep))return 1;
				memcpy(q,w[dep],sizeof(q));
			}
			
		}
	}
	return 0;
}
int main()
{
	int t=0;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		cin>>q[i];
		int dep=0;
		while(dep<5&&!dfs(0,dep))dep++;
		if(dep>=5)
		{
			cout<<"5 or more"<<endl;
		}
		else
		{
			cout<<dep<<endl;
		}
	} 
    return 0;
}

AcWing 181. 回转游戏

https://www.acwing.com/solution/content/4056/

image-20230728233423620

先A后F等于浪费了两次操作，剪枝opposite

op为每个调整的字母对映的位置

center为中间8个数的编号

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1010,N=24;
//char g[maxn][maxn];
int n;
int q[N];
int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int path[100];

int sum[4];
int f()
{
	memset(sum,0,sizeof(sum));
	for(int i=0;i<8;i++)
	{
		sum[q[center[i]]]++;
	}
	int s=0;
	for(int i=1;i<=3;i++)
	{
		s = max(s, sum[i]);
	}
	return 8-s;

}
bool check()
{
    for (int i = 1; i < 8; i ++ )
        if (q[center[i]] != q[center[0]])
            return false;
    return true;
}
void oper(int x)
{
	int t=q[op[x][0]];
	for(int i=0;i<6;i++)q[op[x][i]]=q[op[x][i+1]];
	
	q[op[x][6]] = t;
}
int dfs(int dep,int maxdep,int last)
{
	if(dep+f()>maxdep)return 0;
	if(!f())return 1;
	for(int i=0;i<8;i++)
	{
		if(opposite[i]==last)continue;
		oper(i);
		path[dep]=i;
		if(dfs(dep+1,maxdep,i))return 1;
		oper(opposite[i]);
	}
	return 0;
}
int main()
{
//	int t=0;
//	cin>>t;
	while(cin>>q[0]&&q[0])
	{
		
		for(int i=1;i<N;i++)
			cin>>q[i];
//		cout<<q[0];
		int dep=0;
		while(!dfs(0,dep,-1))dep++;
		if(!dep)
		{
			cout<<"No moves needed";
		}
		for(int i=0;i<dep;i++)
		 	printf("%c", 'A' + path[i]);
		cout<<endl;
		cout<<q[6]<<endl;
	} 
    return 0;
}

谷歌面试（BFS）

给一个m*n大小的矩阵表示地图，两辆车a，b，目的地分别是A，B，地图上用’‘表示道路，‘#’表示墙。

样例1：
a.A
###
b.B
结果：true
样例2:
aBAb
结果：false
样例3:
##.#
aBAb
结果：true

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>

using namespace std;

// 定义状态结构体
struct State {
    int ax, ay; // 车 a 的坐标
    int bx, by; // 车 b 的坐标
};

class Solution {
public:
    bool canReach(vector<string>& grid) {
        int m = grid.size();
        if (m == 0) return false;
        int n = grid[0].size();

        int startAx, startAy, startBx, startBy;
        int targetAx, targetAy, targetBx, targetBy;

        // 1. 解析地图，找到起点和终点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'a') {
                    startAx = i; startAy = j;
                    grid[i][j] = '.'; // 视为平地
                } else if (grid[i][j] == 'b') {
                    startBx = i; startBy = j;
                    grid[i][j] = '.';
                } else if (grid[i][j] == 'A') {
                    targetAx = i; targetAy = j;
                    grid[i][j] = '.';
                } else if (grid[i][j] == 'B') {
                    targetBx = i; targetBy = j;
                    grid[i][j] = '.';
                }
            }
        }

        // 2. BFS 初始化
        // visited[ax][ay][bx][by]
        // 既然是面试，用 vector vector 可能有点繁琐，可以用 flat index 或者多维 vector
        // 这里为了清晰使用多维 vector
        vector<vector<vector<vector<bool>>>> visited(
            m, vector<vector<vector<bool>>>(
                n, vector<vector<bool>>(
                    m, vector<bool>(n, false))));

        queue<State> q;
        q.push({startAx, startAy, startBx, startBy});
        visited[startAx][startAy][startBx][startBy] = true;

        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            State curr = q.front();
            q.pop();

            // 检查是否到达目标
            if (curr.ax == targetAx && curr.ay == targetAy &&
                curr.bx == targetBx && curr.by == targetBy) {
                return true;
            }

            // 策略：尝试移动车 a
            for (auto& d : dirs) {
                int nax = curr.ax + d[0];
                int nay = curr.ay + d[1];

                // 检查边界和墙
                if (nax >= 0 && nax < m && nay >= 0 && nay < n && grid[nax][nay] != '#') {
                    // 关键检查：a 移动后的位置不能是 b 当前的位置
                    if (!(nax == curr.bx && nay == curr.by)) {
                        if (!visited[nax][nay][curr.bx][curr.by]) {
                            visited[nax][nay][curr.bx][curr.by] = true;
                            q.push({nax, nay, curr.bx, curr.by});
                        }
                    }
                }
            }

            // 策略：尝试移动车 b
            for (auto& d : dirs) {
                int nbx = curr.bx + d[0];
                int nby = curr.by + d[1];

                // 检查边界和墙
                if (nbx >= 0 && nbx < m && nby >= 0 && nby < n && grid[nbx][nby] != '#') {
                    // 关键检查：b 移动后的位置不能是 a 当前的位置
                    if (!(nbx == curr.ax && nby == curr.ay)) {
                        if (!visited[curr.ax][curr.ay][nbx][nby]) {
                            visited[curr.ax][curr.ay][nbx][nby] = true;
                            q.push({curr.ax, curr.ay, nbx, nby});
                        }
                    }
                }
            }
        }

        return false;
    }
};

// 测试代码
int main() {
    Solution sol;
    
    // 样例 2: 狭窄通道，无法交换
    vector<string> grid1 = {
        "aBAb" 
    };
    cout << "Example 2 (Expected 0): " << sol.canReach(grid1) << endl;

    // 样例 3: 有避让空间
    vector<string> grid2 = {
        "##.#",
        "aBAb"
    };
    cout << "Example 3 (Expected 1): " << sol.canReach(grid2) << endl;

    return 0;
}