萌新求助
查看原帖
萌新求助
326944
sync_with_stdio楼主2020/8/1 13:43

#11WA

#include<bits/stdc++.h>
using namespace std;
int m,n,sx,sy,ex,ey,minn=99999999;
bool go=false;
int a[105][105],vis[105][105];
int way[10][5]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y,int blood,int step)
{
	if(blood==0)
		return;
	if(a[x][y]==4)
		blood=6;
	if(step>minn)
		return;
	if(x==ex && y==ey)
	{
		minn=min(minn,step);
		go=true;
		return;
	}
	for(int i=0;i<=3;i++)
	{
		int nx=x+way[i][0];
		int ny=y+way[i][1];
		if(nx>m || nx<1 || ny>n || ny<1 || a[nx][ny]==0)
			continue;
		if(vis[nx][ny]==0)
		{
			vis[nx][ny]=1;
			dfs(nx,ny,blood-1,step+1);
			vis[nx][ny]=0;
		}
	}
	return;
}
int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>m>>n;
	int i,j;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==2)
			{
				sx=i;
				sy=j;
			}
			if(a[i][j]==3)
			{
				ex=i;
				ey=j;
			}
		}
	vis[sx][sy]=1;
	dfs(sx,sy,6,0);
	if(go==0)
		cout<<-1;
	else
		cout<<minn; 
	return 0;
}

2020/8/1 13:43
加载中...