小蒟蒻急需dalao的Help!!!SOS!!!
查看原帖
小蒟蒻急需dalao的Help!!!SOS!!!
68960
M_and_P_楼主2020/9/8 23:22

请问哪位Super dalao可以帮蒟蒻一下?laji的蒟蒻感激不尽啊!!

#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int N=105,dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m;
int dis[N][N],color[N][N];
bool vis[N][N];
void dfs(int x,int y,int cost,bool used)
{
	int dx,dy;
	if (cost>=dis[x][y]+2)return ;
	for (int i=0;i<4;i++)
	{
		dx=x+dir[i][0];
		dy=y+dir[i][1];
		if (color[dx][dy]>=4)color[dx][dy]=0;
	}//还原 
	for (int i=0;i<4;i++)
	{
		dx=x+dir[i][0];
		dy=y+dir[i][1];
		if (cost>=dis[dx][dy])continue;
		if (dx>=1&&dx<=n&&dy>=1&&dy<=n&&!vis[dx][dy])
		{
			if (color[dx][dy]==color[x][y]%3&&color[dx][dy]!=0){
				dis[dx][dy]=min(dis[dx][dy],cost);
				vis[dx][dy]=1;
				dfs(dx,dy,cost,0);
				vis[dx][dy]=0;
			}
			if (color[dx][dy]!=color[x][y]%3)
			{
				if (color[dx][dy]==0&&used==0)
				{
					vis[dx][dy]=1;
					color[dx][dy]=color[x][y]+3;
					dis[dx][dy]=min(dis[dx][dy],cost+2);
					dfs(dx,dy,cost+2,1);
					color[dx][dy]=9-(color[x][y]+3);
					dfs(dx,dy,cost+3,1);//用4和5标记用过魔法后的1和2   4%3=1 5%3=2 
					color[dx][dy]=0;
					vis[dx][dy]=0;
				}
				if (color[dx][dy]>0)
				{
					vis[dx][dy]=1;
					dis[dx][dy]=min(dis[dx][dy],cost+1);
					dfs(dx,dy,cost+1,0);
					vis[dx][dy]=0;
				} 
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,model;
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&model);
		model+=1;
		color[x][y]=model;
	}
	vis[1][1]=1;
	
	memset(dis,0x3f,sizeof(dis));
	dis[1][1]=0;
	dfs(1,1,0,0);
	if (dis[n][n]==INF)
	printf("-1");
	else printf("%d",dis[n][n]);
	return 0;
}
2020/9/8 23:22
加载中...