1 条题解

  • 3
    @ 2026-7-26 14:31:37
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    int n,m,mp[100][100],sx,sy,ex,ey,minn=0x3f3f3f3f,step=0;
    char a[100][100];
    int dxd[]{0,0,-1,0,1};
    int dyd[]{0,1,0,-1,0};
    void dfs(int x,int y){
    	if(x==ex && y==ey){
    		minn=min(minn,step);
    		return;
    	}
    	if(mp[x][y]<=step){
    		return;
    	}
    	mp[x][y]=step;
    	for(int i=1;i<=4;++i){
    		int xx,yy;
    		xx=x+dxd[i];
    		yy=y+dyd[i];
    		if(a[xx][yy]!='#'){
    			a[xx][yy]='#';
    			step++;
    			dfs(xx,yy);
    			step--;
    			a[xx][yy]='.';
    		}
    	}
    }
    
    signed main(){
    	cin>>n>>m;
    	memset(a,'#',sizeof(a));
    	memset(mp,0x3f,sizeof(mp));
    	for(int i=1;i<=n;++i){
    		for(int j=1;j<=m;++j){
    			cin>>a[i][j];
    			if(a[i][j]=='@')
    				sx=i,sy=j;
    			if(a[i][j]=='*')
    				ex=i,ey=j;
    		}
    	}
    	a[sx][sy]='#';
    	dfs(sx,sy);
    	if(minn==0x3f3f3f3f){
    		cout<<-1;
    	}
    	else{
    		cout<<minn;
    	}
    	return 0;
    }
    • 1

    信息

    ID
    206
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    4
    已通过
    3
    上传者