洛谷题单1-7 搜索题解_。.‘.i多rf、!:‘1二人;丨、:111w1三∴:!:i:::见∴.:!::心雦$也事i高、::

P1219 [USACO1.5]八皇后 Checker Challenge

这个是我最最开始的写法，也是篇幅最大的写法，每放一个棋子就考虑放这个棋子满不满足 每行每列，左斜线和右斜线都只有一个棋子，注意左斜线和右斜线是有规律的，右斜线的格子横纵坐标和都是一样的，左斜线上的横纵相减是一样的，左斜对角线下的左斜线差小于0，因为数组不能有负数，全加一个他们差的绝对值得最大值（随便一个更大得数也行，不能小），剩下的就是dfs爆搜了，没什么讲的 , 其实有个更简单的写法，但意思是一样的，就不贴上来了

#include<bits/stdc++.h>
using namespace std;
int hang[15]={0},lie[15]={0},zuoxie[50]={0},youxie[50]={0},n,mark=1,count2=0,count1=0;;
vector<int>s1;
void find1(){
	count1++;
	if(count2<=2){
		for(int i=0;i<s1.size();i++){
			printf("%d ",s1[i]);
		}
		printf("\n");
		count2++;
	}
	return ;
}
void dfs(int n,int y){
	lie[y]=1;
	for(int i=1;i<=n;i++){
		if(hang[i]==0&&zuoxie[i-y+14]==0&&youxie[i+y]==0){
			hang[i]=1;
		    zuoxie[i-y+14]=1;
		    youxie[i+y]=1;
		    s1.push_back(i);
		    if(y!=n){
		    	dfs(n,y+1);
			}else find1();
		    s1.pop_back();
		    hang[i]=0;
		    zuoxie[i-y+14]=0;
		    youxie[i+y]=0;		
		}
	}
}


int main(){
	cin>>n;
	dfs(n,1);
	printf("%d",count1);
	return 0;
}
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

P2392 kkksc03考前临时抱佛脚

这个题就是很简单的01背包问题，找一半的钱最多能买多少，再用总钱减去做和就可以了，直接贴代码了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[25],dp[1500];
int main(){
	int s[5],ans=0,q,q2;
	scanf("%d %d %d %d",&s[1],&s[2],&s[3],&s[4]);
	for(int i=1;i<=4;i++){
		memset(dp,0,sizeof(dp));
		memset(a,0,sizeof(a));
		int sum=0;
		for(int j=0;j<s[i];j++){
			scanf("%d",&a[j]);
			sum+=a[j];
		}
		for(int j=0;j<s[i];j++){
			for(int k=sum/2;k>=a[j];k--){
				dp[k]=max(dp[k],dp[k-a[j]]+a[j]);
			}
		}
		ans+=sum-dp[sum/2];
	}
	printf("%d",ans);
	return 0;
}
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

P1443 马的遍历

这个题是一个基础bfs遍历题，马只能走八个方向，直接遍历一遍就可以了，记得剪枝

#include<bits/stdc++.h>
using namespace std;
struct shuang{
	int x,y;
	int step;
};
int a[405][405],b[405][405];
int n,m,x1,y123;
int main(){
	int sx[]={-2,-2,-1,-1,1,1,2,2},sy[]={-1,1,-2,2,-2,2,-1,1};
	shuang q1;
	queue<shuang>s1;
	scanf("%d %d %d %d",&n,&m,&x1,&y123);
	int count=1;
	memset(a,-1,sizeof(a));
	memset(b,0,sizeof(b));
	a[x1][y123]=0;
	b[x1][y123]=1;
	q1.x=x1,q1.y=y123;
	q1.step=0;
	s1.push(q1);
	while(!s1.empty()){
		shuang q2=s1.front();
		s1.pop();
		for(int i=0;i<8;i++){
			int xx=q2.x+sx[i];
			int yy=q2.y+sy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&b[xx][yy]==0){
				shuang q3;
				b[xx][yy]=1;
				q3.x=xx;
				q3.y=yy;
				q3.step=q2.step+1;
				a[xx][yy]=q3.step;
				s1.push(q3);
//				printf("xx=%d yy=%d step=%d\n",xx,yy,q3.step);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%-5d",a[i][j]);
		}
		printf("\n");
	}
	return 0;
}
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

P1135 奇怪的电梯

这个题应该是最经典的bfs了，用结构体记录一下上电梯的次数就行

#include<bits/stdc++.h>
using namespace std;
struct cheng{
	int q;
	int step;
};
int x,n,qi,zhong,mark=0,lc1,lc2,ans;
int a[205],b[205]={0};
int bfs(cheng o){
	queue<cheng>s1;
	s1.push(o);
	while(!s1.empty()){
		cheng m1=s1.front();
		s1.pop();
		if(m1.q==zhong){
			return m1.step;
		}
		lc1=m1.q+a[m1.q];
		if(lc1<=n){
			if(b[lc1]==0){
				b[lc1]=1;
			    cheng m2;
			    m2.q=lc1;
			    m2.step=m1.step+1;
			   s1.push(m2);				
			}

		}
		lc2=m1.q-a[m1.q];
		if(lc2>=1&&b[lc2]==0){
			b[lc2]=1;
			cheng m3;
			m3.q=lc2;
			m3.step=m1.step+1;
			s1.push(m3);
		}		
	}
	return -1;
}
int main(){
	cheng o;
	scanf("%d %d %d",&n,&qi,&zhong);

	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		a[i]=x;
	}
	b[qi]=1;
	o.q=qi,o.step=0;
	ans=bfs(o);
	printf("%d",ans);
	return 0;
}
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

P2895 [USACO08FEB]Meteor Shower S

这个题怎么说呢，我数组一开始卡死在了300，debug了好久，长记性了以后数组开大一些，别卡的那么极限，难点在一开始的数据处理吧，一个地方可能会被不同时间的流星撞，我们要保证记录的是最早的被撞时间，当然，第0秒被撞的直接给他一个大值，后面就是bfs中加一个比对时间就行

#include<bits/stdc++.h>
using namespace std;
struct zou{
	int x,y;
	int time1;
};
zou m1;
int n,x1,y12,t,tmin=100005;
int sx[]={-1,0,1,0},sy[]={0,1,0,-1};
int a[305][305],b[305][305];
void bfs(zou m){
	queue<zou>s1;
	s1.push(m);
	while(!s1.empty()){
		zou m3=s1.front();
		s1.pop();
		if(a[m3.x][m3.y]==0){
			tmin=m3.time1;
			return ;
		}
		for(int i=0;i<4;i++){
			zou q3;
			int xx=m3.x+sx[i];
			int yy=m3.y+sy[i];
			if(xx>=0&&xx<=302&&yy>=0&&yy<=302&&b[xx][yy]==0){
				if(a[xx][yy]==0||m3.time1+1<a[xx][yy]){
					b[xx][yy]=1;
					q3.x=xx;
					q3.y=yy;
					q3.time1=m3.time1+1;
					s1.push(q3);
				}
			}
		}
	}
}
int main(){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	b[0][0]=1;
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d %d %d",&x1,&y12,&t);
		if(a[x1][y12]==0){
			a[x1][y12]=t;
		}
		if(a[x1][y12]>t){
			a[x1][y12]=t;
		}
		for(int j=0;j<4;j++){
			int q1=x1+sx[j];
			int q2=y12+sy[j];
			if(q1>=0&&q2>=0){
				if(a[q1][q2]==0){
					a[q1][q2]=t;
					if(t==0){
						a[q1][q2]=100000;
					}
				}else if(a[q1][q2]>t){
					a[q1][q2]=t;
					if(t==0){
						a[q1][q2]=100000;
					}					
				}
			}
		}
	}
	m1.time1=0;
	m1.x=0;
	m1.y=0;
	bfs(m1); 
	if(tmin==100005){
		printf("-1");
	}else printf("%d",tmin);
	return 0;
}
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

P1036 [NOIP2002 普及组] 选数

这个题目我也没有想到什么特别好的方法，直接爆搜的

#include<bits/stdc++.h>
using namespace std;
int x[20],n,k;
bool is(int n){
    int s=sqrt(double(n));
    for(int i=2;i<=s;i++){
        if(n%i==0)return false;
    }
    return true;
}
int rule(int m1,int sum1,int start,int end){//m1是还有几个数每加,sum1为和,start是当前是第几个数,end是一共有几个数 
    if(m1==0)return is(sum1);
    int sum=0;
    for(int i=start;i<=end;i++){
        sum+=rule(m1-1,sum1+x[i],i+1,end);
    }
    return sum;
}
int main(){
    cin>>n>>k;
    for(int i =0;i<n;i++)cin>>x[i];
    cout<<rule(k,0,0,n-1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

P2036 [COCI2008-2009#2] PERKET

这个就是一个选与不选的问题，也是直接dfs爆搜就行，当然最开始的数据处理给他单个食材的最小差值比较好

#include<bits/stdc++.h>
using namespace std;
int n,minn=10000000;
struct shicai{
	int suandu,kudu;
	int cha;
};
shicai s1[11];
void dfs(int i,int suan,int ku){
	if(abs(suan-ku)<minn&&ku!=0){
		minn=abs(suan-ku);
	}
	if(i>=n){
		return ;
	}	
	dfs(i+1,suan*s1[i].suandu,ku+s1[i].kudu);
	dfs(i+1,suan,ku);
	return ;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d %d",&s1[i].suandu,&s1[i].kudu);
		s1[i].cha=abs(s1[i].suandu-s1[i].kudu);
		if(s1[i].cha<minn){
			minn=s1[i].cha;
		}
	}
	dfs(0,1,0);
	printf("%d",minn);
	return 0;
}
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

P1433 吃奶酪

说到这个题那我可就起劲了，首先我们要知道什么是状压思想，我们不是一共有n个奶酪吗，我们假设一个数字，这个数字转化成二进制有n位，我们令他对应的位为1时表示吃过了这个奶酪，那么我们每一个数字对应的二进制状态就是已经吃了几个奶酪，我们把每个状态，即1到n个1（二进制）遍历一遍，就是所有吃奶酪过程中可能出现的状态，然后在每个状态中把能更新的距离都更新一遍，就有状态方程

F(i,k)=min ( F ( i , k ) , F ( i , k - (i-1<<1) ) +a[ i ] [ j ] )

即从 j 点到 i 点距离的更新，k是状态，我们要保证k是经过 i 点的，而且没到 i 点前没经过 i 点，这听起来很像废话，但这就是细节，我们怎么保证呢？
（ k-( 1<< ( i-1 ) ) ）& ( 1<< ( i-1 ) ) = = 0，表示没经过这个点，但是注意了，我们现在是更新后的点，即我们现在是k状态，即我们要保证上面成立 ，要先保证 k & ( 1<< ( i-1 ) ) = = 1成立，其实就是你要先到达这个点了，才知道不经过这个点，从其他已经经过的点到达这能不能更新距离，建议配合代码理解，死看是八行的

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define db double
using namespace std;
int n;
db x[20],y[20];
db f[18][34000];//一维表示最后在那个点，二维表示此时的状态，经过了几个点
db a[20][20];
db d(int q,int w){
	return sqrt(pow(x[q]-x[w],2)+pow(y[q]-y[w],2));
}
int main(){
	int i,j,k;
	double ans;
	memset(f,127,sizeof(f));
	ans=f[0][0];
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%lf %lf",&x[i],&y[i]);
	}
	x[0]=0;y[0]=0;	
	for(i=0;i<=n;i++){
		for(j=i+1;j<=n;j++){
			a[i][j]=d(i,j);
			a[j][i]=a[i][j];
		}
	}
	for(i=1;i<=n;i++){
		f[i][(1<<(i-1))]=a[0][i];//从0到i点的单纯两点距离
	}
	for(k=1;k<(1<<n);k++){
		for(i=1;i<=n;i++){
			if((k&(1<<(i-1)))==0){
				continue;
			}
			for(int j=1;j<=n;j++){
				if(i==j){
					continue;
				}
				if(k&(1<<(j-1))==0){
					continue;
				}
				f[i][k]=min(f[i][k],f[j][k-(1<<(i-1))]+a[i][j]);// 从j点到i点 
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans=min(ans,f[i][(1<<n)-1]);
	}
	printf("%.2lf",ans);
	return 0;
}
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

P1605 迷宫

这个题也不多说了，没有新意的dfs爆搜

#include<cstdio>
#include<queue>
#include<cstring>
int a[10][10],sx[]={-1,1,0,0},sy[]={0,0,-1,1},vis[10][10];
int n,m,t,ans=0,qix,qiy,zhongx,zhongy,t1,t2;
void dfs(int x,int y){
	if(x==zhongx&&y==zhongy){
		ans++;
		return ;
	}
	for(int i=0;i<4;i++){
		int xx=x+sx[i];
		int yy=y+sy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]==0){
			vis[xx][yy]=1;
			dfs(xx,yy);
			vis[xx][yy]=0;
		}
	}
}
int main(){
	memset(a,0,sizeof(a));
	memset(vis,0,sizeof(vis));
	scanf("%d %d %d",&n,&m,&t);
	scanf("%d %d %d %d",&qix,&qiy,&zhongx,&zhongy);
	for(int i=0;i<t;i++){
		scanf("%d %d",&t1,&t2);
		a[t1][t2]=1;
	}
	vis[qix][qiy]=1;
	dfs(qix,qiy);
	printf("%d",ans);
	return 0;
}
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

P1019 [NOIP2000 提高组] 单词接龙

这个题我是卡在比较重叠字母那里了，后来得到大佬指点，我们可以从一个字母开始比较，直到比到最多的字母完全相同，返回这个数字，不断递归更新一个最长长度与是否更新，直到把所有能接龙的都遍历一遍就可以了

对了对了，主函数那个空格是为了防止是以单个字母来开始接龙（重叠函数要求最短长度也要为2）

#include<cstdio>
#include<cstring>
#include<iostream>
int n,vis[25]={0},len=0;
using namespace std;
string str[25];
int chongdie(string str1,string str2){
	for(int i=1;i<min(str1.length(),str2.length());i++){//比几个字母 
		int mark=1;
		for(int j=0;j<i;j++){
			if(str1[str1.length()-i+j]!=str2[j]){//这个位置的字母不重叠，没办法接龙 
				mark=0;
				break;
			}
		}
		if(mark){
			return i;
		}
	}
	return 0;
}
void search(string str1,int lens){
	int c;
	len=max(len,lens);
	for(int i=0;i<n;i++){
		if(vis[i]>=2){
			continue;
		}		
		c=chongdie(str1,str[i]);
		if(c>0){
			vis[i]++;
			search(str[i],lens+str[i].length()-c);
			vis[i]--;
		}		
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<=n;i++){
		cin>>str[i];
	}
	search(' '+str[n],1);
	printf("%d",len);
	return 0;
}
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

P1101 单词方阵

我这里没想到什么特别好的方法，就是找到有y的地方，往所有方向走六步，假如与izhong相等那就是对的，在b数组里赋值一下即可

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
char a[105][105],b[105][105];
int sx[]={-1,-1,-1,0,0,1,1,1},sy[]={-1,0,1,-1,1,-1,0,1},n,k=0;
int x[10005],y[10005];
char s1[]={"gnohzi"};
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			b[i][j]='*';
			cin>>a[i][j];
			if(a[i][j]=='y'){
				x[k]=i;
				y[k++]=j;
			}
		}
	}
	while(k--){
		for(int i=0;i<8;i++){
			int mark=1;
			int xx=x[k]+(sx[i]*6);
			int yy=y[k]+(sy[i]*6);
			if(xx>=0&&xx<n&&yy>=0&&yy<n){
				for(int j=5;j>=0;j--){
					if(a[xx-(sx[i]*j)][yy-(sy[i]*j)]!=s1[j]){
						mark=0;
					}
				}
				if(mark){
					b[x[k]][y[k]]='y';
					for(int j=1;j<=6;j++){
						b[x[k]+(sx[i]*j)][y[k]+(sy[i]*j)]=s1[5-(j-1)];
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			printf("%c",b[i][j]);
		}
		printf("\n");
	}
	return 0;
}
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

P2404 自然数的拆分问题

这个题，需要一点细节，看了代码就会写

#include<cstdio>
#include<cstring>
int n;
int a[10000]={1};
void shuchu(int t){
	for(int i=1;i<t;i++){
		printf("%d+",a[i]);
	}
	printf("%d\n",a[t]);
}
void find(int x,int t){
	for(int i=a[t-1];i<=x;i++){
		if(i<n){
			a[t]=i;
		    x-=i;
	    	if(x==0){
			    shuchu(t);
		     }else find(x,t+1);
		    x+=i;
		}
	}
}
int main(){
    scanf("%d",&n);
	find(n,1);	
	return 0;
}
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

P1596 [USACO10OCT]Lake Counting S

这个题没怎么细想，直接记录一下所有有水的地方（直接爆搜怕TLE），然后对每个有水的地方开始bfs并标记，然后从下一个没有被标记的有水的地方继续bfs

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<utility>
using namespace std;
int vis[105][105],x[11000],y[11000],k=0,ans=0,n,m;
int sx[]={-1,-1,-1,0,0,1,1,1},sy[]={-1,0,1,-1,1,-1,0,1};
char a[105][105];
queue<pair<int,int> >s1;
int main(){
	memset(vis,0,sizeof(vis));
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j]!='W'){
				vis[i][j]=1;
			}else {
				x[k]=i;
				y[k++]=j;
			}
		}
	}
	for(int i=0;i<k;i++){
		if(vis[x[i]][y[i]]){
			continue;
		}
		vis[x[i]][y[i]]=1;
		ans++;
		s1.push({x[i],y[i]});
		while(!s1.empty()){
			pair<int,int>t=s1.front();
			s1.pop();
			for(int j=0;j<8;j++){
				int xx=t.first+sx[j];
				int yy=t.second+sy[j];
				if(xx>=0&&xx<n&&yy>=0&&yy<m&&vis[xx][yy]==0){
					vis[xx][yy]=1;
					s1.push({xx,yy});
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}
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

P1162 填涂颜色

这个题其实我不算写出来，我的思路有问题，但刚好测试数据没出到，我算是卡着数据过的，因为它中间会用1卡出一个闭环，那么我们把外面所有的0都标记一下，最后遍历一遍，没有被标记的0就在闭环里面，变成2就好，但是如果直接就是最外面就是闭环或者直接（1，1）是1，我这个就不成立了
仅供参考吧

#include<cstdio>
#include<iostream>
using namespace std;
int a[35][35],b[35][35],x[1000],y[1000],k=0;
int sx[]={-1,1,0,0};
int sy[]={0,0,-1,1};
int n,i,j;
void dfs(int p,int q){
    int i;
    if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return;
    a[p][q]=1;
    for (i=0;i<4;i++){
    	dfs(p+sx[i],q+sy[i]);
	}
}
int main(){
    cin>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            cin>>b[i][j];
            if (b[i][j]==0){
            	x[k]=i;
            	y[k++]=j;
            	a[i][j]=0;
			}
            else a[i][j]=2;
        }
    dfs(0,0);
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
        	if(a[i][j]==0){
        		printf("2 ");
			}else printf("%d ",b[i][j]);
		}
		printf("\n");
    }
    return 0;
}
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

P1032 [NOIP2002 提高组] 字串变换

这个题用优先队列和map加substr过的（substr函数用不用都行，能写就行）
a.substr(3,5)表示a这个字符串的第三位开始的后五位 , 这题综合性挺强的

#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
int vis[7];
string b[7],c[7];
string a,ans;
int k=0;
map<string,int>map1;
struct node {
	string x;
	int step;
};
struct cmp{
	bool operator()(node a,node b){
		return a.step>b.step;
	}
};
string jia(string &str,int i,int j){
	string ans="";
	if(i+b[j].length()>str.length()){
		return ans;
	}
	for(int p=0;p<b[j].length();p++){
		if(str[i+p]!=b[j][p]){
		    //cout<<"qwq"<<" "<<"str[i]="<<str[i]<<" p="<<p<<" c[j][p]="<<c[j][p]<<endl;
			return ans;
		}
	}
	ans=str.substr(0,i);
	ans+=c[j];
	ans+=str.substr(i+b[j].length());
	return ans;
}
void bfs(){
	priority_queue<node,vector<node>,cmp>q;	
	q.push({a,0});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		if(map1.count(t.x)==1){
			continue;
		}
		if(t.x==ans){
			printf("%d\n",t.step);
			return ;
		}
		if(t.step>10){
			break;
		}
		map1[t.x]=1;
		for(int i=0;i<t.x.length();i++){
			for(int j=0;j<k;j++){
				string ans=jia(t.x,i,j);
				if(ans!=""){
					q.push({ans,t.step+1});
				}
			}
		}
	}
	printf("NO ANSWER!\n");
	return ;
}
int main(){
	cin>>a>>ans;
	while(cin>>b[k]>>c[k]){
		k++;
	}
	bfs();
	return 0;
}
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

P1825 [USACO11OPEN]Corn Maze S

这个题一开始到传送站我直接让他移动而且把两边都标记了，直接wa了，后来仔细想了一下，传送未必是好事，而且也不一定只传送一次，当然最多两次（过去或者回来），那我们在遍历的时候对有字母的特判一下就行，只标记传送过来的传送点（出发传送点），然后把当前的坐标变为传送后的点，这样再上下左右移动还会有一次回去来判断有没有更近的，其他的就是简单的迷宫了

#include<queue>
#include<iostream>
#include<string>
#include<map>
#include<cstring>
#include<cstdio>
#include<utility>
using namespace std;
int vis[500][500];
char a[500][500];
struct node{
	int x;
	int y;
	int step;
};
struct cmp{
	bool operator()(node a,node b){
		return a.step>b.step;
	} 
};
int n,m,qix,qiy;
int sx[]={-1,0,0,1},sy[]={0,-1,1,0};
node find(int x,int y,int st){
	node ans;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
		//	printf("%d %d\n",a[x][y],a[i][j]);
			if(a[i][j]==a[x][y]&&(i!=x||y!=j)){
				ans.x=i;
				ans.y=j;
				ans.step=st;
				return ans;
			}
		}
	}
}
void bfs(){
	node t2;
	priority_queue<node,vector<node>,cmp>q;
	q.push({qix,qiy,0});
	while(!q.empty()){
		node t=q.top();
		q.pop();
//		printf("%d %d\n",t.x,t.y);
		if(a[t.x][t.y]=='='){
			printf("%d\n",t.step);
			return ;
		}
		if(vis[t.x][t.y]==1){
			continue;
		}
		vis[t.x][t.y]=1;
		if(a[t.x][t.y]>='A'&&a[t.x][t.y]<='Z'){
			t=find(t.x,t.y,t.step);
		}
		for(int i=0;i<4;i++){
			int xx=t.x+sx[i];
			int yy=t.y+sy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0&&a[xx][yy]!='#'){
			//	printf("jin l %d %d\n",xx,yy);
			    q.push({xx,yy,t.step+1});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){
				qix=i;
				qiy=j;
			}
		}
	}
	bfs();
	return 0;
}
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

总的来说搜索这东西，暴力出奇迹，偏分过样例 ，就吃一个熟练度，你多敲几个题目就会越来越得心应手，还是要加油啊，米娜桑