Naoqi robot summary 26

Basic algorithm

Breadth first search （BFS） And depth first search （DFS） Algorithm analysis _Chida15 The blog of -CSDN Blog _bfs Algorithm

1003- Simulated campaign _2021 Autumn algorithm introductory class Chapter 6 exercises ： Search and search pruning (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int size[N];
char s[N][N];
int vis[N][N];
int dx[8]={0,1,0,-1,-1,1,1,-1};
int dy[8]={1,0,-1,0,1,1,-1,-1};
int m,cnt;
int a[N],b[N],tot,tot1;
void   dfs(int x,int y,int &ans,int k)
{// For every cannon attacked , So it's centered 3*3 The squares will be affected , So find the connected block , The number of each connected block , And the number of cannons in each connected block .
	if(s[x][y]=='.') return ;
	vis[x][y]=true;
	for(int i=0;i<8;i++)
	{
		int xx=dx[i]+x;
		int yy=dy[i]+y;
		if(xx<k||xx>=k+4||yy<0||y>=m||vis[xx][yy]) continue;
		vis[xx][yy]=true;
		if(s[xx][yy]=='*') ans++;
		dfs(xx,yy,ans,k);

	}
}
int main()
{
	cin>>m;
	for(int i=0;i<8;i++) cin>>s[i];
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]=='*'&&!vis[i][j])
			{
				cnt=1;
				dfs(i,j,cnt,0);	
				a[++tot]=cnt;
			}
		}
	}
	for(int i=4;i<8;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]=='*'&&!vis[i][j])
			{
				cnt=1;
				dfs(i,j,cnt,4);
				b[++tot1]=cnt;
			}
		}
	}
	if(tot1<tot) cout<<-1<<endl;
	else
	{

		sort(b+1,b+1+tot1);
		int ans=0;
		for(int i=tot;i<=tot1;i++) ans+=b[i];
		cout<<ans<<endl;
	}
}

1002- Out of the maze _2021 Autumn algorithm introductory class Chapter 6 exercises ： Search and search pruning (nowcoder.com)

#include <bits/stdc++.h>
const int maxn = 510;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
char a[maxn][maxn];
bool visited[maxn][maxn];
bool flag=false;
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void dfs(int x,int y){
    if(a[x][y]=='E'){
        flag=true;
        return ;
    }
    if(flag==true) return ;
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if((a[nx][ny]=='.'||a[nx][ny]=='E')&&!visited[nx][ny]){
            visited[nx][ny]=true;
            dfs(nx,ny);
        }
    }
}

int main()
{
    while(cin>>n>>m){
        memset(visited,false,sizeof(visited));
        memset(a,-1,sizeof(a));
        for(int i=1;i<=n;i++){
            scanf("%s",a[i]+1);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]=='S'){
                    flag=false;
                    visited[i][j]=true;
                    dfs(i,j);
                    break;
                }
            }
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}