Java教程

专题一搜索 A - Biggest Number

本文主要是介绍专题一搜索 A - Biggest Number，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
  1. 题目
    You have a maze with obstacles and non-zero digits in it:

    You can start from any square, walk in the maze, and finally stop at some square. Each step, you
    may only walk into one of the four neighbouring squares (up, down, left, right) and you cannot
    walk into obstacles or walk into a square more than once. When you finish, you can get a number by
    writing down the digits you encounter in the same order as you meet them. For example, you can get
    numbers 9784, 4832145, etc. The biggest number you can get is 791452384, shown in the picture above.
    Your task is to find the biggest number you can get.
    Input
    There will be at most 25 test cases. Each test begins with two integers R and C (2 ≤ R,C ≤ 15,
    R ∗ C ≤ 30), the number of rows and columns of the maze. The next R rows represent the maze. Each
    line contains exactly C characters (without leading or trailing spaces), each of them will be either ‘#’
    or one of the nine non-zero digits. There will be at least one non-obstacle squares (i.e. squares with a
    non-zero digit in it) in the maze. The input is terminated by a test case with R = C = 0, you should
    not process it.
    Output
    For each test case, print the biggest number you can find, on a single line.
    Sample Input
    3 7
    ##9784#
    ##123##
    ##45###
    0 0
    Sample Output
    791452384
  2. 思路
    直接深搜要超时，所以要剪枝，网上有什么深搜结合广搜的写法，但是如果只是想过题的话简单剪一剪就好了
    数字之间比较大小，先比位数，位数多的大，位数相同再从头到尾比较，所以找位数最长的比较就行，当前搜到的答案比最佳的短直接不比较，比最佳的长那它就是新的最佳，位数相同就逐位比较
    对于地图上的每个数，全部记录下来排个序，从大到小搜，同时记录当前最佳答案的长度，如果最佳答案长度已经和地图上数字总数量一样多了，那把当前最佳答案的首位数字做起点的数列搜完就可以不搜了，比如当前最佳答案是791452384，那把“7”做起点的所有序列搜完就跳出了
    另外数字只有非0的个位数，为了自己读入和处理方便，可以把#号读入的时候直接记为0，vis直接设为1
  3. 代码
    #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

struct node{
	int x,y;
};
struct node mov[4]={{-1,0},{0,1},{1,0},{0,-1}};

struct spot{
	int num;
	int x,y;
}sp[35];

bool cmp(spot x,spot y){
    return x.num>y.num;
}

int n,m;
int vis[35][35];
int map[35][35];
int nx,ny;

int ans[100];//最长路径
int ansl;//最长路径长度
int now[100];//当前查找路径
int nowl;//当前查找路径长度

bool check(int x,int y)
{
	if(x>=1&&x<=n&&y>=1&&y<=m){
		return 1;
	}
	return 0;
}

void dfs(int x,int y)
{
	bool walk=0;
	for(int i=0;i<=3;i++)
	{
		int nx=x+mov[i].x;
		int ny=y+mov[i].y;
		if(vis[nx][ny]==0&&check(nx,ny))
		{
			walk=1;
			vis[nx][ny]=1;
			now[nowl]=map[nx][ny];
			nowl++;
//			for(int j=0;j<nowl;j++)
//			{
//				printf("%d",now[j]);
//			}
//			printf("\n");
			dfs(nx,ny);
			nowl--;
//			for(int j=0;j<nowl;j++)
//			{
//				printf("%d",now[j]);
//			}
//			printf("\n");
			vis[nx][ny]=0;
		}
	}
	if(walk==0)
	{
		if(nowl>ansl)
		{
			for(int j=0;j<nowl;j++)
			{
				ans[j]=now[j];
			}
			ansl=nowl;
		}
		else if(nowl==ansl)
		{
			bool flag=0;
			for(int j=0;j<nowl;j++)
			{
				if(now[j]>ans[j])
				{
					flag=1;
					break;
				}
				else if(now[j]<ans[j])
					break;
			}
			if(flag)
			{
				for(int j=0;j<nowl;j++)
				{
					ans[j]=now[j];
				}
			}
		}
	}
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF&&n!=0&&m!=0)
	{
		memset(vis,0,sizeof(vis));
		memset(now,0,sizeof(now));
		memset(ans,0,sizeof(ans));
		memset(map,0,sizeof(map));
		memset(sp,0,sizeof(sp));
		ansl=0;
		char c;
		int tot=0;
		getchar();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%1c",&c);
				if(c=='#')
				{
					map[i][j]=0;
					vis[i][j]=1;
				}
				else
				{
					map[i][j]=c-'0';
					sp[tot].num=map[i][j];
					sp[tot].x=i;
					sp[tot].y=j;
					tot++;
				}
			}
			getchar();
		}
		sort(sp,sp+tot-1,cmp);
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				printf("%d",vis[i][j]);
//			}
//			printf("\n");
//		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				printf("%d",map[i][j]);
//			}
//			printf("\n");
//		}
//		bool f=1;
//		for(int u=9;u>=1&&f;u--)
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				if(map[i][j]==u){
//					//printf("%d,%d\n",i,j);
//					nowl=1;
//					now[0]=map[i][j];
//					vis[i][j]=1;
//					dfs(i,j);
//					vis[i][j]=0;
//				}
//				if(ansl==tot){
//					f=0;
//				}
//			}
//		}
		for(int i=0;i<tot;i++){
			int x=sp[i].x;
			int y=sp[i].y;
			nowl=1;
			now[0]=map[x][y];
			vis[x][y]=1;
			dfs(x,y);
			vis[x][y]=0;
			if(ansl==tot&&ans[0]>sp[i].num){
				break;
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				if(map[i][j]!=0){
//					//printf("%d,%d\n",i,j);
//					nowl=1;
//					now[0]=map[i][j];
//					vis[i][j]=1;
//					dfs(i,j);
//					vis[i][j]=0;
//				}
//			}
//		}
		if(ansl==0)
		{
			printf("0");
		}
		for(int i=0;i<ansl;i++)
		{
			printf("%d",ans[i]);
		}
		printf("\n");
	}
	return 0;
}
这篇关于专题一搜索 A - Biggest Number的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航