简单搜索 ua_深度优先搜索经典例题「建议收藏」

简单搜索 ua_深度优先搜索经典例题「建议收藏」…_1.7e+1+2.4j.imag

简单搜索

A – Dungeon Master

Description – 题目描述

XHK被困在一个三维的网吧中,现在要寻找最短路径逃生! 空间由立方体单位构成 你每次向上下前后左右移动一个单位需要一分钟 你不能对角线移动并且四周封闭 是否存在逃出生天的可能性?如果存在,则需要多少时间?

 Input – 输入

  输入第一行是一个数表示空间的数量。   每个空间的描述的第一行为L,R和C(皆不超过30)。   L表示空间的高度。   R和C分别表示每层空间的行与列的大小。   随后L层地牢,每层R行,每行C个字符。   每个字符表示空间的一个单元。’#’表示不可通过单元,’.’表示空白单元。你的起始位置在’S’,出口为’E’。   每层空间后都有一个空行。L,R和C均为0时输入结束。

 Output – 输出

  每个空间对应一行输出。
  如果可以逃生,则输出如下
Escaped in x minute(s).
  x为最短脱离时间。

  如果无法逃生,则输出如下
Trapped!

 Sample Input – 输入样例

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

 Sample Output – 输出样例

Escaped in 11 minute(s).
Trapped!

第一遍写的时候居然想到的是深搜,然后爆时间了才想起来用广搜

打个板子出来就完了

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int x[6]={1,-1,0,0,0,0};
int y[6]={0,0,1,-1,0,0};
int z[6]={0,0,0,0,1,-1};
int Gmap[33][33][33];
int opx=0,opy=0,opz=0,tip=0,edx=0,edy=0,edz=0;
int gima,kima,cima;
int min=27001;

void nmm(int bs){
	if(Gmap[edx][edy][edz]>0) return;
	int tip=0;
	int imai,imaj,imak;
	for(int i=0;i<gima;i++){
		for(int j=0;j<kima;j++){
			for(int k=0;k<cima;k++){
				if(Gmap[i][j][k]==bs){
					for(int sb=0;sb<6;sb++){
						imai=i+x[sb];
						imaj=j+y[sb];
						imak=k+z[sb];
						if(imai>=0&&imai<gima&&imaj>=0&&imaj<kima&&imak>=0&&imak<cima){
							if(Gmap[imai][imaj][imak]==0) Gmap[imai][imaj][imak]=bs+1;
							tip=1;
						}
					}
				}
			}
		}
	}
	
	if(tip==0) return;
	else nmm(bs+1);
}

void find(int gao,int kuan,int chang){
	gima=gao;kima=kuan;cima=chang;
	for(int i=0;i<33;i++) for(int j=0;j<33;j++) for(int k=0;k<33;k++) Gmap[i][j][k]=0;
	char ima;
	opx=0,opy=0,opz=0,tip=0,edx=0,edy=0,edz=0;
	min=27001;
	for(int i=0;i<gao;i++){
		for(int j=0;j<kuan;j++){
			getchar();
			for(int k=0;k<chang;k++){
				scanf("%c",&ima);
				if(ima=='S'){
					opx=i,opy=j,opz=k;
					Gmap[i][j][k]=1;
				}
				else if(ima=='E'){
					edx=i,edy=j,edz=k;
					Gmap[i][j][k]=0;
				}
				else if(ima=='.') Gmap[i][j][k]=0;
				else Gmap[i][j][k]=-1;
			}
		}
		getchar();
	}
	
	nmm(1);
	if(Gmap[edx][edy][edz]) printf("Escaped in %d minute(s).\n",Gmap[edx][edy][edz]-1);
	else printf("Trapped!\n");
}

int main()
{
	int gao,kuan,chang;
	scanf("%d%d%d",&gao,&kuan,&chang);
	while(gao!=0&&kuan!=0&&chang!=0){
		find(gao,kuan,chang);
		scanf("%d%d%d",&gao,&kuan,&chang);
	}
	return 0;
}

B – Fliptile

农夫约翰知道,一头知识上满意的母牛是一头快乐的母牛,它将提供更多的牛奶。他为母牛安排了脑力活动,他们在其中操纵M × N 网格(1≤ M ≤15; 1≤ N ≤15)个正方形瓷砖,每个瓷砖的一面都涂成黑色,另一面则涂成白色。

正如人们所猜测的那样,当翻转单个白色瓷砖时,它会改变变黑翻转单个黑色图块时,它会变为白色。母牛在翻转砖块时会得到奖励,因此每块砖块的白色侧面都朝上。但是,母牛的蹄子相当大,当他们尝试翻转特定的砖块时,它们也会翻转所有相邻的砖块(与翻转后的砖块共享整个边缘的砖块)。由于翻转很累,奶牛希望尽量减少必须做的翻转次数。

帮助母牛确定所需的最小翻转次数,并确定要达到最小翻转次数的位置。如果有多种方法可以以最少的翻转次数来完成任务,则当将其视为字符串时,以输出中词典顺序最少的方式返回。如果无法完成任务,请用“ IMPOSSIBLE”一词打印一行。

第1行:两个以空格分隔的整数: M 和 N
第2 .. M +1行:第 i +1行描述了网格中第i行( N 以空格分隔的整数,黑色为1,白色为0。

 Output

第1 .. M 行:每行包含 N 个以空格分隔的整数,每个整数指定翻转该特定位置的次数。

 Sample Input

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

 Sample Output

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

1.根据该方块上下左右的操作次数和它原来的颜色判断其当前颜色

2.第一行有n的长度,所以对第一行所有可能的操作方式有2^n种,通过取二进制数在相应位置的数与1进行按位与运算来对每种方式进行记录

建议使用样例:

3 3

1 0 0

1 0 1

0 0 1

结果:

0 1 1

0 0 0

1 1 0

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int m,n,ima=0;
int g[20][20]={0};
int imag[20][20]={0};
int end[20][20]={0};
int min=0x3f3f3f3f;

int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};

int imaabs(int aa,int bb){
	int sb=0;
	for(int i=0;i<5;i++){
		int a=aa+xx[i],b=bb+yy[i];
		if(a>=0&&b>=0&&a<m&&b<n){
			sb+=imag[a][b];
		}
	}
	sb+=g[aa][bb];
	return sb%2;
}

int find(){
	ima=0;
	for(int i=0;i<n;i++)  ima+=imag[0][i];
	for(int i=1;i<m;i++){
		for(int j=0;j<n;j++){
			if(imaabs(i-1,j)){
				imag[i][j]=1;
				ima++;
			}
			else imag[i][j]=0;
		}
	}
//	printf("______________\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++){
//			printf("%d ",imag[i][j]);
//		}
//		printf("\n");
//	}
	for(int i=0;i<n;i++){
		if(imaabs(m-1,i)) return 0;
	}
	return 1;
}

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&g[i][j]);
		}
	}
	for(int k=0;k< 1<<n;k++){
		memset(imag,0,sizeof(imag));
		for(int i=0;i<n;i++){
			imag[0][i]=k>>i&1;
		}
		if(find()&&ima<min){
			for(int i=0;i<m;i++){
				for(int j=0;j<n;j++){
					end[i][j]=imag[i][j];
				}
			}
			min=ima;
		}
	}
	if(min==0x3f3f3f3f) printf("IMPOSSIBLE");
	else{
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				printf("%d ",end[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

 C – Find The Multiple

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int ok=0;
int num;

void find(int ima,long long int x){
	if(ima>19||ok==1) return;
	if(x%num==0){
		printf("%lld\n",x);
		ok=1;
		return;
	}
	find(ima+1,x*10);
	find(ima+1,x*10+1);
}

int main()
{
	while(scanf("%d",&num),num!=0){
		ok=0;
		find(1,1);
	}
	return 0;
}

D – Shuffle’m Up

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>
#include <map>
using namespace std;


char a[105],b[105],c[205],d[205];


int main() {
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		int l;scanf("%d\n%s\n%s\n%s",&l,a,b,c);
		map<string,int> ok;
		int p=0,add=0,num=0;
		while(1){
			add++;
			num=0;
			for(int j=0;j<l;j++){
				d[num++]=b[j];
				d[num++]=a[j];
			}
			d[num]=0;
			if(strcmp(d,c)==0) break;
			if(ok[d]==1){
				p=1;break;
			}
			ok[d]=1;
			for(int j=0;j<l;j++){
				a[j]=d[j];
				b[j]=d[j+l];
			}
			a[l]=b[l]=0;
		}
		printf("%d ",i);
		if(p) printf("-1\n");
		else printf("%d\n",add);
	}
	return 0;
}

E – Pots

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>
#include <map>
using namespace std;

char jz[6][10]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int zt[300][300]={0},tip[300][300]={0},last[300][300][2]={0};
int minn=9999;
int a,b,c,nmm=0;
int ok[200]={0};
int endi=0,endj=0;

void find(int bs){
	int ima=0;
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			if(zt[i][j]==bs){
				ima=1;
				if(zt[i][b]==0){
					zt[i][b]=bs+1;tip[i][b]=1;last[i][b][0]=i;last[i][b][1]=j;
				}
				if(zt[a][j]==0){
					zt[a][j]=bs+1;tip[a][j]=0;last[a][j][0]=i;last[a][j][1]=j;
				}
				if(zt[i][0]==0){
					zt[i][0]=bs+1;tip[i][0]=3;last[i][0][0]=i;last[i][0][1]=j;
				}
				if(zt[0][j]==0){
					zt[0][j]=bs+1;tip[0][j]=2;last[0][j][0]=i;last[0][j][1]=j;
				}
				if(zt[i+j][0]==0){
					zt[i+j][0]=bs+1;tip[i+j][0]=5;last[i+j][0][0]=i;last[i+j][0][1]=j;
				}
				if(zt[0][i+j]==0){
					zt[0][i+j]=bs+1;tip[0][i+j]=4;last[0][i+j][0]=i;last[0][i+j][1]=j;
				}
				if(i-(b-j)>=0){
					if(zt[i-(b-j)][b]==0){
						zt[i-(b-j)][b]=bs+1;tip[i-(b-j)][b]=4;last[i-(b-j)][b][0]=i;last[i-(b-j)][b][1]=j;
					}
				}
				if(j-(a-i)>=0){
					if(zt[a][j-(a-i)]==0){
						zt[a][j-(a-i)]=bs+1;tip[a][j-(a-i)]=5;last[a][j-(a-i)][0]=i;last[a][j-(a-i)][1]=j;
					}
				}
				if(i==c||j==c) {
					endi=i;endj=j;
					return;
				}
			}
		}
	}
	if(ima) find(bs+1);
}


int main() {
	
	scanf("%d%d%d",&a,&b,&c);
	zt[0][0]=1;
	find(1);
	
	if(endi==0&&endj==0) printf("impossible");
	else{
		printf("%d\n",zt[endi][endj]-1);
		int l=zt[endi][endj];
		while(endi!=0||endj!=0){
			ok[zt[endi][endj]]=tip[endi][endj];
			int aa=last[endi][endj][0],bb=last[endi][endj][1];
			endi=aa;endj=bb;
		}
		for(int i=0;i<=a;i++){
			//for(int j=0;j<=b;j++) printf("%d ",zt[i][j]);
			//printf("\n");
		}
		//printf("\n");
		for(int i=0;i<=a;i++){
			//for(int j=0;j<=b;j++) printf("%d ",tip[i][j]);
			//printf("\n");
		}
		//printf("\n");
		for(int i=0;i<=a;i++){
			//for(int j=0;j<=b;j++) printf("%d*%d  ",last[i][j][0],last[i][j][1]);
			//printf("\n");
		}
		//printf("\n");
		for(int i=2;i<=l;i++) printf("%s\n",jz[ok[i]]);
	}
	return 0;
}

F – Oil Deposits

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int m,n;
int g[110][110]={0},t[110][110]={0};
int max=1;
int x[8]={-1,0,1,-1,1,-1,0,1};
int y[8]={1,1,1,0,0,-1,-1,-1};


void find(int a,int b){
	t[a][b]=max;
	int xx,yy;
	for(int k=0;k<8;k++){
		xx=a+x[k];yy=b+y[k];
		if(xx>=0&&xx<m&&yy>=0&&yy<n){
			if(t[xx][yy]==0){
				if(g[xx][yy]) find(xx,yy);
				t[xx][yy]=max;
			}
		}
	}
}


int main()
{
	char x;
	while(scanf("%d%d",&m,&n),m!=0&&n!=0){
		max=1;
		for(int i=0;i<m;i++){
			getchar();
			for(int j=0;j<n;j++){
				t[i][j]=0;
				scanf("%c",&x);
				if(x=='@') g[i][j]=1;
				else g[i][j]=0;
			}
		}
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(g[i][j]==1&&t[i][j]==0){
					find(i,j);
					max++;
				}
			}
		}
		printf("%d\n",max-1);
	}
	return 0;
}

 G – Find a way

伊菲的家在乡下,而梅基的家在市中心。于是,伊菲和梅基安排在KFC见面。西安有很多KFC,他们想选择一个花费总时间最短的KFC见面。
现在给你一张西安的地图,伊菲和梅基都可以上、下、左、右移动到相邻的地点,每移动一个位置花费11分钟。

Input

输入包含多个测试用例。
每个测试用例包括前两个整数n,m.(2<=n,m<=200)。
接下来的n行,每行包含m个字符。
“Y”表示伊菲的初始位置。
“M”表示梅基初始位置。
“#”死路;
‘.’可走的路。
“@” KCF

Output

对于每个测试用例,输出伊菲和梅基花费的最短总时间。总有一家KFC可以让他们见面。

Sample Input

4 4
Y.#@
….
.#..
@..M
4 4
Y.#@
….
.#..
@#.M
5 5
Y..@.
.#…
.#…
@..M.
#…#

Sample Output

66
88
66

敲广搜板子

什么傻逼题面给个省略号

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int m,n;
int GY[210][210]={0},GM[210][210]={0},KFC[210][210]={0};
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1};


void tip(int x){
	int ok=0;
	int a,b;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(GY[i][j]==x){
				for(int k=0;k<4;k++){
					a=i+xx[k];b=j+yy[k];
					if(a>=0&&a<m&&b>=0&&b<n){
						if(GY[a][b]==0) {
							GY[a][b]=x+1;
							ok=1;
						}
					}
				}
			}
			if(GM[i][j]==x){
				for(int k=0;k<4;k++){
					a=i+xx[k];b=j+yy[k];
					if(a>=0&&a<m&&b>=0&&b<n){
						if(GM[a][b]==0) {
							GM[a][b]=x+1;
							ok=1;
						}
					}
				}
			}
		}
	}
	if(ok) tip(x+1);
	else return;
}



void find(){
	tip(1);
	int min=40001;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(KFC[i][j]&&GY[i][j]&&GM[i][j]){
				//printf("%d %d\n",i,j);
				min=min<GY[i][j]+GM[i][j]?min:GY[i][j]+GM[i][j];
			}
		}
	}
	printf("%d\n",(min-2)*11);
}


int main()
{
	while(~scanf("%d%d",&m,&n)){
		memset(GY,0,sizeof(GY));
		memset(GM,0,sizeof(GM));
		memset(KFC,0,sizeof(KFC));
		char x;
		for(int i=0;i<m;i++){
			getchar();
			for(int j=0;j<n;j++){
				scanf("%c",&x);
				if(x=='.'){
					GY[i][j]=GM[i][j]=0;
				}
				else if(x=='Y'){
					GY[i][j]=1;
					GM[i][j]=0;
				}
				else if(x=='M'){
					GY[i][j]=0;
					GM[i][j]=1;
				}
				else if(x=='#'){
					GY[i][j]=GM[i][j]=-1;
				}
				else if(x=='@'){
					KFC[i][j]=1;
					GY[i][j]=GM[i][j]=0;
				}
			}
		}
		find();
	}
	return 0;
}

 J – 哈密顿绕行世界问题

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>
#include <map>
#include <set>
using namespace std;

int num[22][4]={0};
int tip[22]={0},js[22]={0};
int ip=1;
int endd;

void find(int xx,int nn){
	if(nn==20){
		for(int i=1;i<=3;i++){
			if(num[xx][i]==endd){
				printf("%d:  ",ip);
				ip++;
				printf("%d ",endd);
				for(int j=1;j<=19;j++) printf("%d ",js[j]);
				printf("%d\n",endd);
			}
		}
	}
	else{
		for(int i=1;i<=3;i++){
			if(tip[num[xx][i]]==0&&num[xx][i]!=endd){
				tip[xx]=1;
				js[nn]=num[xx][i];
				find(num[xx][i],nn+1);
				tip[num[xx][i]]=0;
			}
		}
	}
}

int main() {
	int k;
	for(int i=1;i<=20;i++) {
		for(int j=1;j<=3;j++) scanf("%d",&num[i][j]);
		sort(num[i],num[i]+3);
		
		
	}
	int x;
	scanf("%d",&x);
	while(x!=0){
		memset(tip,0,sizeof(tip));
		endd=x;
		ip=1;
		find(x,1);
		scanf("%d",&x);
	}
	return 0;
}

M – A计划

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int GA[15][15]={0},GB[15][15]={0},GC[15][15]={0};
int m,n,time;
int endi,endj,endc;
int x[4]={1,-1,0,0};
int y[4]={0,0,1,-1};
char sb[20];


void bfs(int bs){
	int tip=0;
	int aa,bb;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(GA[i][j]==bs){
				for(int k=0;k<4;k++){
					aa=i+x[k];bb=j+y[k];
					if(aa>=0&&aa<m&&bb>=0&&bb<n){
						if(GA[aa][bb]==0){
							GA[aa][bb]=bs+1;
							if(GC[aa][bb]==2) {
								if(GB[aa][bb]==0) GB[aa][bb]=GA[aa][bb];
								else GB[aa][bb]=GB[aa][bb]<GA[aa][bb]?GB[aa][bb]:GA[aa][bb];
								GA[aa][bb]=0;
							}
							tip=1;
						}
					}
				}
			}
			if(GB[i][j]==bs){
				for(int k=0;k<4;k++){
					aa=i+x[k];bb=j+y[k];
					if(aa>=0&&aa<m&&bb>=0&&bb<n){
						if(GB[aa][bb]==0){
							GB[aa][bb]=bs+1;
							if(GC[aa][bb]==1) {
								if(GA[aa][bb]==0) GA[aa][bb]=GB[aa][bb];
								else GA[aa][bb]=GA[aa][bb]<GB[aa][bb]?GA[aa][bb]:GB[aa][bb];
								GB[aa][bb]=0;
							}
							tip=1;
						}
					}
				}
			}
		}
	}
	if(tip) bfs(bs+1);
	else return;
}


void find(){
	memset(GA,0,sizeof(GA));
	memset(GB,0,sizeof(GB));
	memset(GC,0,sizeof(GC));
	scanf("%d%d%d",&m,&n,&time);
	char x;
	for(int i=0;i<m;i++){
		gets(sb);
		for(int j=0;j<n;j++){
			scanf("%c",&x);
			if(x=='S') GA[i][j]=1;
			else if(x=='P') {
				GA[i][j]=0;endi=i;endj=j;endc=1;
			}
			else if(x=='*') GA[i][j]=-1;
			else if(x=='#') GC[i][j]+=2,GA[i][j]=0;
			else GA[i][j]=0;
		}
	}
	gets(sb);
	for(int i=0;i<m;i++){
		gets(sb);
		for(int j=0;j<n;j++){
			scanf("%c",&x);
			if(x=='S') GB[i][j]=1;
			else if(x=='P') {
				GA[i][j]=0;endi=i;endj=j;endc=2;
			}
			else if(x=='*') GB[i][j]=-1;
			else if(x=='#') GC[i][j]+=1,GB[i][j]=0;
			else GB[i][j]=0;
		}
	}
	GA[0][0]=1;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(GC[i][j]==3||GA[i][j]==-1||GB[i][j]==-1) {
				if(GC[i][j]==3) GA[i][j]=GB[i][j]=-1;
				else if(GA[i][j]==-1&&GC[i][j]==1) GB[i][j]=-1;
				else if(GB[i][j]==-1&&GC[i][j]==2) GA[i][j]=-1;
				GC[i][j]=0;
			}
		}
	}
//	printf("------------------\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++) printf("%3d",GA[i][j]);
//		printf("\n");
//	}
//	printf("------------------\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++) printf("%3d",GB[i][j]);
//		printf("\n");
//	}
//	printf("------------------\n");
	bfs(1);
	if(endc==1){
		if(GA[endi][endj]-1<=time&&GA[endi][endj]>0) printf("YES\n");
		else printf("NO\n");
	}
	else{
		if(GB[endi][endj]-1<=time&&GB[endi][endj]>0) printf("YES\n");
		else printf("NO\n");
	}
//	printf("------------------\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++) printf("%3d",GA[i][j]);
//		printf("\n");
//	}
//	printf("------------------\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++) printf("%3d",GB[i][j]);
//		printf("\n");
//	}
//	printf("------------------\n");
//	for(int i=0;i<m;i++){
//		for(int j=0;j<n;j++) printf("%3d",GC[i][j]);
//		printf("\n");
//	}
//	printf("------------------\n");
}

int main()
{
	int t;scanf("%d",&t);
	while(t--) find();
	return 0;
}

P – Beat

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <iostream>
#include <map>
#include <set>
using namespace std;
int g[20][20]={0};
int tip[20]={0};
int n;

int maxx=0;

void find(int num,int last,int bs){
	if(bs>maxx) maxx=bs;
	tip[num]=bs;
	//for(int i=1;i<=n;i++) printf("%d ",tip[i]);
	//printf("\n");
	for(int i=2;i<=n;i++){
		if(tip[i]>0) continue;
		if(g[num][i]>=last){
			find(i,g[num][i],bs+1);
		}
	}
	tip[num]=0;
}

void fuck(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) scanf("%d",&g[i][j]);
	}
		find(1,0,1);
	printf("%d\n",maxx);
}


int main() {
	while(~scanf("%d",&n)){
		memset(g,0,sizeof(g));
		memset(tip,0,sizeof(tip));
		maxx=0;
		fuck();
	}
	return 0;
}

 T – Open the Lock

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int nmdwsm;
int na[4],nb[4];

void js(int a,int b,int c,int d,int bs){
	int end=a*1000+b*100+c*10+d;
	int add=bs;
	if(abs(nb[0]-a)<=4) add+=abs(nb[0]-a);
	else add+=9-abs(nb[0]-a);
	if(abs(nb[1]-b)<=4) add+=abs(nb[1]-b);
	else add+=9-abs(nb[1]-b);
	if(abs(nb[2]-c)<=4) add+=abs(nb[2]-c);
	else add+=9-abs(nb[2]-c);
	if(abs(nb[3]-d)<=4) add+=abs(nb[3]-d);
	else add+=9-abs(nb[3]-d);
	if(add<nmdwsm) nmdwsm=add;
}

void find(int a,int b,int c,int d,int bs){
	if(bs>5) return;
	js(a,b,c,d,bs);
	find(b,a,c,d,bs+1);
	find(a,c,b,d,bs+1);
	find(a,b,d,c,bs+1);
//	find((a+1==10?1:a+1),b,c,d,bs+1);//不用管加减1的情况
//	find((a-1==0?9:a-1),b,c,d,bs+1);
//	find(a,(b+1==10?1:b+1),c,d,bs+1);
//	find(a,(b-1==0?9:b-1),c,d,bs+1);
//	find(a,b,(c+1==10?1:c+1),d,bs+1);
//	find(a,b,(c-1==0?9:c-1),d,bs+1);
//	find(a,b,c,(d+1==10?1:d+1),bs+1);
//	find(a,b,c,(d-1==0?9:d-1),bs+1);
}

void fuck(){
	nmdwsm=9999;
	int a,b;scanf("%d%d",&a,&b);
	for(int i=3;i>=0;i--){
		na[i]=a%10;
		nb[i]=b%10;
		a/=10;b/=10;
	}
	find(na[0],na[1],na[2],na[3],0);
	printf("%d\n",nmdwsm);
}

int main()
{
	int tt;
	scanf("%d",&tt);
	while(tt--) fuck();
	return 0;
}

U – 速算24点

强行写个全排列,写了一坨屎山都能过

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<malloc.h>

int ys(int x,int a,int b){
	if(x==1) return a+b;
	else if(x==2) return a-b;
	else if(x==3) return b-a;
	else if(x==4) return a*b;
	else if(x==5) {
		if(b!=0&&a%b==0) return a/b;
		else return 9999;
	}
	else if(x==6){
		if(a!=0&&b%a==0) return b/a;
		else return 9999;
	}
	return 9999;
}

int main()
{
	char oppp[4][4];
	int num[4]={0},tip[4]={0};
	while(~scanf("%s %s %s %s",oppp[0],oppp[1],oppp[2],oppp[3])){
		getchar();
		int ok=0;
		memset(num,0,sizeof(num));
		memset(tip,0,sizeof(tip));
		for(int i=0;i<4;i++){
			int l=strlen(oppp[i]);
			if(l==2) num[i]=10;
			else{
				if(oppp[i][0]=='A') num[i]=1;
				else if(oppp[i][0]=='J') num[i]=11;
				else if(oppp[i][0]=='Q') num[i]=12;
				else if(oppp[i][0]=='K') num[i]=13;
				else num[i]=oppp[i][0]-'0';
			}
		}
		int a,b,ab,c,abc,d,abcd,cd,end=0;
		for(int i=0;i<4;i++){
			a=num[i];tip[i]=1;
			for(int j=0;j<4;j++){
				if(tip[j]==0){
					tip[j]=1;
					b=num[j];
					for(int k=1;k<=6;k++){
						ab=ys(k,a,b);
						if(ab==9999) continue;
						for(int ii=0;ii<4;ii++){
							if(tip[ii]==0){
								tip[ii]=1;
								c=num[ii];
								for(int jj=1;jj<=6;jj++){
									abc=ys(jj,ab,c);
									if(abc==9999) continue;
									for(int kk=0;kk<4;kk++){
										if(tip[kk]==0){
											d=num[kk];
											for(int iii=1;iii<=6;iii++){
												abcd=ys(iii,abc,d);
												if(abcd==24) end=1;
												if(end==1) break;
											}
										}
										if(end==1) break;
									}
									if(end==1) break;
								}
								for(int jj=0;jj<4;jj++){
									if(tip[jj]==0){
										d=num[jj];
										for(int kk=1;kk<=6;kk++){
											cd=ys(kk,c,d);
											if(cd==9999) continue;
											for(int iii=1;iii<=6;iii++){
												abcd=ys(iii,ab,cd);
												if(abcd==24) end=1;
												if(end==1) break;
											}
											if(end==1) break;
										}
									}
									if(end==1) break;
								}
								tip[ii]=0;
							}
							if(end==1) break;
						}
						if(end==1) break;
					}
					tip[j]=0;
				}
				if(end==1) break;
			}
			tip[i]=0;
			if(end==1) break;
		}
		if(end) printf("Yes\n");
		else printf("No\n");
		
	}
	
	
	return 0;
}

今天的文章简单搜索 ua_深度优先搜索经典例题「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/65663.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注