木头

用户名：taozi123

访问量：1931

签　名：

等　　级
排　　名	4194
经　　验	1742
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	啊啊啊
专　　业

　　自我简介：

TA的其他文章

Biggest Number-题解（C语言代码）时间超限
浏览：694

你可能喜欢

Biggest Number-题解（C语言代码）时间超限

　　作者: 木头　　　　发表时间：2020-05-05 11:28:46 浏览：694　|　评论：1　

原题链接：Biggest Number

这道题，时间超限是个问题，，回溯法由于试探过程中大量递归调用，消耗的栈资源和时间资源比较多，于是用循环方式实现，结果还是时间超限，后面优化一下看看，笑。。。。。。。
    没办法了，只能上代码了
    第一个是循环方式
	1、由于输入部分是字符，咱们索性就用字符数组，直接按最大的来【15】【15】
	2、我们需要自己建一个栈，来存储信息，每个栈元素需要存储坐标i,j ，方向td,当前坐标的字符ch.
	3、方向td用0123，分别代表四个方向，我们设定都从0开始，顺时针搜索
	
	循环方式
	#include <stdio.h>
#include <string.h>
//栈元素结构体
struct _Node{
	char ch;//存储坐标位置的字符
	int i,j;// 坐标
	int td;// 方向
}ArrNode[31];//总元素30，那么多给1个呗
int top=-1;//栈针，全局变量
int r,c;//全局变量，行和列
char Array[15][15]={0};//我们的字符数组，存储检索的二维数据
char result[31]={0};//保存结果
char temp[31]={0};//零时结果，与result进行比较
void findMax(int i,int j);
int main(){
	int i,j;
	
	fflush(stdin);
	while(scanf("%d%d",&r,&c)){
		if(0==r || 0==c)
			break;

for(i=0;i<r;i++){
			fflush(stdin);
			for(j=0;j<c;j++){
				Array[i][j]=getchar();	
			}
		}
		//我们需要用一个循环，让所有的有效数据，都做一次头
		for(i=0;i<r;i++){
			for(j=0;j<c;j++){
				if('#'!=Array[i][j]){
					findMax(i,j);
				}	
			}
		}
		//输出结果result
		printf("%s\n",result);
	}
}

void findMax(int i,int j){
	int x,y,d,find,tip;
	//头元素入栈
	top++;
	ArrNode[top].ch=Array[i][j];//这里的记录当前坐标的字符，是为了后面恢复该位置
	ArrNode[top].i=i;
	ArrNode[top].j=j;
	ArrNode[top].td=-1;
	Array[i][j]='#';//入栈后，为了下一次不会再折回该点，需要改变二维数组，(i,j)的值，设为'#'
	//整个代码块是个while大循环，只要栈中有元素，就需要循环
	while(top>-1){
		x=ArrNode[top].i;
		y=ArrNode[top].j;
		d=ArrNode[top].td;//取出方向d，为下面的判断做准备
		
		find=0;//设置一个标记
		while(d<4 && 0==find){
			d++;
			switch(d){
				case 0:
						x=ArrNode[top].i-1;
						y=ArrNode[top].j;
						break;
				case 1:
						x=ArrNode[top].i;
						y=ArrNode[top].j+1;
						break;
				case 2:
						x=ArrNode[top].i+1;
						y=ArrNode[top].j;
						break;
				case 3:
						x=ArrNode[top].i;
						y=ArrNode[top].j-1;
						break;
			}
			//判断新坐标 x,y是否合法，否则就接着找，直到方向d>3，说明走人死胡同了
			if(x>=0 && x<r && y>=0 && y<c && Array[x][y]!='#') 
				find=1;//修改标记
		}
		//标记find的作用就在下面代码里，如果找到了新方向，就把新元素入栈。如果没找到，d>3，说明走入死胡同了，那么需要检索栈中元素组成的字符串
		if(1==find){
			ArrNode[top].td=d;
			top++;
			ArrNode[top].i=x;
			ArrNode[top].j=y;
			ArrNode[top].td=-1;
			ArrNode[top].ch=Array[x][y];
			Array[x][y]='#';

}else{
			tip=top;
			temp[tip+1]='\0';//设置字符temp的结束符
			while(tip>-1){
				temp[tip]=ArrNode[tip].ch;//把栈中的字符从栈顶开始给temp
				tip--;
			}
			//比较temp和sresult谁大，1、长度更长的显然更大
			if(strlen(temp)>strlen(result)){
				strcpy(result,temp);
			}
			//2、长度一样，就比字符大小，
			if(strlen(temp)==strlen(result)){
				if(strcmp(temp,result)>0){
					strcpy(result,temp);
				}
			}
			//走入死胡同，就需要弹栈了，弹栈之前需要恢复一下被弹的位置
			Array[ArrNode[top].i][ArrNode[top].j]=ArrNode[top].ch;
			top--;
		}
	}
}

下面是回溯法。
1、根据需要，在堆上分配空间，构建二维数组，数组元素是个结构体，tip用来标记是否走过这个点
2、使用了三级指针，希望小伙伴们不要迷惘。
3、其实，这里面很多内容可以简化掉。尤其是构建二维数组，以及对标记tip的处理方式
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum{false,true} bool;
typedef struct _Node{
	char date;
	char tip;
}Node,*pNode;
int Max=0;
int r,c;

void creatTable(Node ***Table);
void findMax(Node ***Table,int temp,int i,int j);
bool ligitimate(Node ***Table,int i,int j);
void reflashTable(Node ***Table);
int main(){
	Node **Table=NULL;
	int max=0;
	int i,j;
	fflush(stdin);
	while(scanf("%d %d",&r,&c)){
		if(0==r || 0==c)
			break;
		
		creatTable(&Table);

for(i=0;i<r;i++){
			for(j=0;j<c;j++){
				if(ligitimate(&Table,i,j)){
					findMax(&Table,0,i,j);
					reflashTable(&Table);
				}
				
			}	
		}

printf("%d\n",Max);
		if(!Table){
			for(i=0;i<r;i++){
				if(!Table[i]){
					free(Table[i]);
				}	
			}
			free(Table);
		}		
	}

return 0;
}

void findMax(Node ***Table,int temp,int i,int j){	
		temp=temp+(int)((*Table)[i][j].date - '0');
		(*Table)[i][j].tip='1';
		if(temp>Max){
			Max=temp;
		}

if(ligitimate(Table,i,j+1)){
			findMax(Table,temp*10,i,j+1);		
			(*Table)[i][j+1].tip='0';
		}

if(ligitimate(Table,i,j-1)){
			findMax(Table,temp*10,i,j-1);
			(*Table)[i][j-1].tip='0';
		}

if(ligitimate(Table,i+1,j)){
			findMax(Table,temp*10,i+1,j);
			(*Table)[i+1][j].tip='0';
		}
			
		if(ligitimate(Table,i-1,j)){
			findMax(Table,temp*10,i-1,j);
			(*Table)[i-1][j].tip='0';
		}	
}
void reflashTable(Node ***Table){
	int i,j;
	for(i=0;i<r;i++){
		for(j=0;j<c;j++){
			if((*Table)[i][j].date!='#'){
				(*Table)[i][j].tip='0';
			}
		}
	}
}
bool ligitimate(Node ***Table,int i,int j){
	return (i>=0 && i<r && j>=0 && j<c && (*Table)[i][j].date!='#' && (*Table)[i][j].tip=='0');
}
void creatTable(Node ***Table){
	int i,j;
	
	*Table=(Node **)malloc(r*sizeof(Node*));
	for(i=0;i<r;i++){
		(*Table)[i]=(Node*)malloc(c*sizeof(Node));
	}

for(i=0;i<r;i++){
		fflush(stdin);
		for(j=0;j<c;j++){
			(*Table)[i][j].date=getchar();
			(*Table)[i][j].tip='0';
		}	
	}	
}

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

六十二

好厉害

2021-02-23 16:14:28

木头

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

小九九（C语言代码）

Tom数（C语言代码）

川哥的吩咐（C语言代码）

P1002 （C语言代码）

Biggest Number-题解（C语言代码）时间超限

评论区

精彩推荐

C语言训练-角谷猜想（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

水仙花（C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1071题解

IP判断（C语言代码）

木头

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C++代码）

小九九 （C语言代码）

Tom数 （C语言代码）

川哥的吩咐 （C语言代码）

P1002 （C语言代码）

Biggest Number-题解（C语言代码）时间超限

评论区

精彩推荐

C语言训练-角谷猜想 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

水仙花 （C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1071题解

IP判断 （C语言代码）

小九九（C语言代码）

Tom数（C语言代码）

川哥的吩咐（C语言代码）

　　评论区

C语言训练-角谷猜想（C语言代码）

C语言考试练习题_保留字母（C语言代码）

水仙花（C语言代码）

IP判断（C语言代码）