68分求救,P2802,WA6 7 10 12
  • 板块灌水区
  • 楼主ztyo_zysclown
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/18 20:58
  • 上次更新2023/11/3 02:48:34
查看原帖
68分求救,P2802,WA6 7 10 12
947854
ztyo_zysclown楼主2023/8/18 20:58
#include<bits/stdc++.h>
using namespace std;
int n,m;
int sum=1e9;
int sum1=sum;
int a[10][10];
int fx[4]={0,0,-1,1};
int fy[4]={1,-1,0,0};
int op=0;
int dx,dy;
void dfs(int x,int y,int ans,int s){
	if(x==dx&&y==dy){
		sum=min(sum,s);
		return;
	}
	if(s>=sum||op>=n*m/2){
		return ;
	}
	if(ans>1){
		for(int i=0;i<4;i++){
			int tx=x+fx[i];
			int ty=y+fy[i];
			if(tx>=0&&ty>=0&&tx<n&&ty<m&&a[tx][ty]!=0&&op<=11){
				op++;
				if(a[x][y]==4){
		            dfs(x,y,6,s+1);
	            }
	            else{
	            	dfs(tx,ty,ans-1,s+1);
				}
				op--;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	int o,p;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j]==2){
				o=i;
				p=j;
			}
			if(a[i][j]==3){
				dx=i;
				dy=j;
			}
		}
	}
	dfs(o,p,6,0);
	if(sum==sum1){
		cout<<"-1";
	}
	else{
		cout<<sum;
	}
} 
2023/8/18 20:58
加载中...