1 条题解

  • 0
    @ 2023-11-21 21:13:42
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};
    int m,n;
    int chess[105][105];
    bool vis[105][105];
    int ans[105][105];
    void dfs(int x,int y,int col,int mag,int sum){
    	if(sum>=ans[x][y]) return ;
    	ans[x][y]=sum;
    	if(x==m&&y==m){
    		return ;
    	}
    	for(int i=0;i<4;i++){
    		int nx=x+dx[i],ny=y+dy[i];
    		if(nx<1||nx>m||ny<1||ny>m||vis[nx][ny]==1) continue;
    		if(chess[nx][ny]==col){
    			vis[nx][ny]=1;
    			dfs(nx,ny,col,0,sum);
    			vis[nx][ny]=0;
    		}else if(chess[nx][ny]==-1){
    			if(mag==0){
    				vis[nx][ny]=1;
    				dfs(nx,ny,col,1,sum+2);
    				vis[nx][ny]=0;
    			}
    		}else{
    			vis[nx][ny]=1;
    			dfs(nx,ny,chess[nx][ny],0,sum+1);
    			vis[nx][ny]=0;
    		}
    
    	}
    }
    
    int main(){
    	memset(chess,-1,sizeof(chess));
    	memset(ans,0x3f,sizeof(ans));
    	int x,y,c;
    	cin>>m>>n;
    	for(int i=1;i<=n;i++){
    		cin>>x>>y>>c;
    		chess[x][y]=c;
    	}
    	vis[1][1]=1;
    	dfs(1,1,chess[1][1],0,0);
    	if(ans[m][m]==0x3f3f3f3f){
    		cout<<-1;
    	}else{
    		cout<<ans[m][m];
    	}
    	return 0;
    }
    

    信息

    ID
    706
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    81
    已通过
    25
    上传者