DFS #3#4TLE #5WA
查看原帖
DFS #3#4TLE #5WA
1188358
Yosuga_sora楼主2024/3/2 11:26
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int n;
char a[110][110]={0},b[110][110]={0};
int stepx[8]={0,1,1,1,0,-1,-1,-1};
int stepy[8]={1,1,0,-1,-1,-1,0,1};
char str[8]={"yizhong"};
int c[8][3]={0};
bool check(int x,int y){
	if(x<0||y<0||x>=n||y>=n){
		return 0;
	}
	return 1;
}
void dps(int x,int y,int num,int sx,int sy){
	if(num==6){
		c[num][0]=x;
		c[num][1]=y;
		for(int i=0;i<7;i++){
			b[c[i][0]][c[i][1]]=a[c[i][0]][c[i][1]];
		}		
		return ;
	}
	if(a[x][y]!=str[num]){
		for(int i=0;i<3;i++){
			if(check(x+stepx[i],y+stepy[i])){
				dps(x+stepx[i],y+stepy[i],0,0,0);
			}
		}
	}
	else{
		c[num][0]=x;
		c[num][1]=y;
		for(int i=0;i<8;i++){
			if(check(x+stepx[i],y+stepy[i])){
				if(num==0){
					if(a[x+stepx[i]][y+stepy[i]]==str[num+1]){
						dps(x+stepx[i],y+stepy[i],num+1,stepx[i],stepy[i]);
					}				
				}
				else{
					if(a[x+stepx[i]][y+stepy[i]]==str[num+1]&&stepx[i]==sx&&stepy[i]==sy){
						dps(x+stepx[i],y+stepy[i],num+1,stepx[i],stepy[i]);
					}
				}
			}			
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s",a[i]);
		for(int j=0;j<n;j++){
			b[i][j]='*';
		}
	}
	dps(0,0,0,0,0);
	for(int i=0;i<n;i++){
		printf("%s",b[i]);
		printf("\n");
	}
	return 0;
}
2024/3/2 11:26
加载中...