这题DFS也能卡过去啊
查看原帖
这题DFS也能卡过去啊
558350
Sunhaisheng2009楼主2024/10/23 16:15

吸氧能通过
不吸氧70

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,sx,sy,ans[105][105],cnt=0;
char Map[105][105];
int l[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
inline void dfs(int x,int y,int step){
    ans[x][y]=step;
    int tx,ty;
    for(register int i=0;i<8;++i){
        tx=x+l[i][0]; ty=y+l[i][1];
        if(tx<1||tx>n||ty<1||ty>m){
        	continue;
		}if(Map[tx][ty]=='*'){
        	continue;
		}if(step+1>=ans[tx][ty]){
        	continue;
		}
        dfs(tx,ty,step+1);
    }
}
int main(){
    scanf("%d%d%d%d",&m,&n,&sy,&sx);
    for(register int i=1;i<=n;++i){
    	for(register int j=1;j<=m;++j){
    		ans[i][j]=998244353;
		}
	}
    for(register int i=n;i>0;--i){
    	for(register int j=1;j<=m;++j){
      		cin>>Map[i][j];
	  	}
	}
    dfs(sx,sy,0); 
    for(register int i=1;i<=n;++i){
    	for(register int j=1;j<=m;++j){
      		if(Map[i][j]!='*'){
      			cnt=max(cnt,ans[i][j]);
			}
	  	}
	}
	printf("%d",cnt);
    return 0;
}
2024/10/23 16:15
加载中...