2 solutions

  • 0
    @ 2022-3-20 19:42:02

    bfs不太会,我强行用了dfs

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,x,y,sx,sy,fx,fy;
    char ma1[25][25];
    int ans[10005];//记录每个到达终点的cnt的值
    bool ma2[25][25];//记录是否走过 
    int opx[5] = {1,0,0,-1};
    int opy[5] = {0,1,-1,0};
    int cnt,op=0;//cnt 用于计数 ans 用于记录最小的路径 
    void dfs(int x,int y){
    	if(x == fx && y == fy){
    		ans[op] = cnt;
            op++;
            
    	}
    	else{
    		for(int i = 0; i < 4; i++){
    			int nex = x + opx[i];
    			int ney = y + opy[i];
    			if(nex>=1&&nex<=n&&ney>=1&&ney<=m&&(ma1[nex][ney]=='.'||ma1[nex][ney]=='*')&&!ma2[nex][ney]){
    				ma2[nex][ney] = true;
    				cnt++; 
    				dfs( nex, ney);
    				ma2[nex][ney] = false;
                    cnt--;
    			}
    		}
    	}
    }
    int main(){
    	std::ios::sync_with_stdio(false);
    	cin>>n>>m;
    	for(int i = 1; i <= n; i++){
    		for(int j = 1; j <= m; j++){
    			cin>> ma1[i][j];
    			if(ma1[i][j]=='@')
    				sx = i,sy = j;
    			if(ma1[i][j]=='*')
    				fx = i, fy = j;
    		}
    	}
    	dfs( sx, sy);
        int mini=100005;
        for(int i=0;i<100;i++){
            if(ans[i]&&ans[i]<mini)
                mini=ans[i];
        }
        if(mini != 100005)
    	    cout<<mini;
       else
           cout<<-1;
    	return 0;
    }
    

    Information

    ID
    1236
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    6
    Tags
    # Submissions
    151
    Accepted
    48
    Uploaded By