#1 MLE求助
  • 板块P2802 回家
  • 楼主D_xbang
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/24 11:30
  • 上次更新2024/11/24 14:04:38
查看原帖
#1 MLE求助
1130163
D_xbang楼主2024/11/24 11:30
#include <bits/stdc++.h>
using namespace std;
int n,m,a[10][10],flag[10][10],ans;
int qx,qy,zx,zy,minn=1e6+1;
int dx[] = {-1,0,1,0},dy[] = {0,-1,0,1};
void dfs(int x,int y,int h/*血*/,int time) {
	if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]&&flag[x][y]<h&&h){
		if(x==zx&&y==zy){
			minn=min(minn,time);
			ans++;
			return ;
		}
		if (a[x][y]==4){
			h=6;
		}
		int mm=flag[x][y];//回溯 
		flag[x][y]=h;
		for (int i=0;i<4;i++) {
			dfs(x+dx[i], y+dy[i],h-1,time+1);
		}
		flag[x][y]=mm;
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]==2){//起 
				qx=i,qy=j;
			}
			else if(a[i][j]==3){//终 
				zx=i,zy=j;
			}
		}
	}
	dfs(qx,qy,6,0);
	if (minn==1e6+1&&ans==0){
		cout<<-1;
	}
	else {
		cout<<minn;
	}
	return 0;
}

#1

in:

9 9 2 0 1 4 1 1 4 1 1 1 0 4 1 1 4 1 1 1 1 4 1 1 4 1 1 1 4 4 1 1 4 1 4 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 4 1 4 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 4 1 1 1 1 1 3

out:

-1

2024/11/24 11:30
加载中...