灌水
  • 板块灌水区
  • 楼主Jaim
  • 当前回复9
  • 已保存回复9
  • 发布时间2020/9/5 17:01
  • 上次更新2023/11/5 13:41:59
查看原帖
灌水
197498
Jaim楼主2020/9/5 17:01

这个代码的复杂度是O(n^2)吗?

#include<iostream>
#include<cstdio>
using namespace std;
int n,c[2]={0,1};
char a[101][101],b[8]="yizhong";
bool d[101][101];
void dfs(int x,int y,int num,int ca,int s,int w)
{
	bool flag=0;
	if(ca==1)
	{	
		if(num==6) for(int i=0;i<7;i++)	d[x-s*i][y-w*i]=1;
		if(num<6)
		{
			if(a[x+s][y+w]==b[num+1]) 
			{
				dfs(x+s,y+w,num+1,1,s,w);
				flag=1;
			}
			if(flag==0) return;
		}
	}
	if(ca==0)
	{	
		if(num==0) for(int i=0;i<7;i++)	d[x-s*i][y-w*i]=1;
		if(num>0)
		{
			if(a[x+s][y+w]==b[num-1]) 
			{
				dfs(x+s,y+w,num-1,0,s,w);
				flag=1;
			}
			if(flag==0) return;
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++) 
	{
		cin>>a[i][j];
		d[i][j]=0;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]==b[0])
		{
			for(int ii=0;ii<2;ii++)
			for(int jj=0;jj<2;jj++)
			if(a[i+c[ii]][j+c[jj]]==b[1]) dfs(i+c[ii],j+c[jj],1,1,c[ii],c[jj]);
		}
		if(a[i][j]==b[6])
		{
			for(int ii=0;ii<2;ii++)
			for(int jj=0;jj<2;jj++)
			if(a[i+c[ii]][j+c[jj]]==b[5]) dfs(i+c[ii],j+c[jj],5,0,c[ii],c[jj]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(d[i][j]==0) cout<<"*";
			else cout<<a[i][j];
		}
		cout<<endl;
	}
	return 0;
}
2020/9/5 17:01
加载中...