全RE,求调
查看原帖
全RE,求调
554576
yueluoxingchen楼主2024/7/9 16:53
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

const int N=105,M=20;
int xx,yy,mk[N][N],dp[N][N],stx,sty,res,cnt;
int xy[12][2]={{-2,-1},{-2,-2},{-1,-2},{1,-2},{2,-2},{2,-1},{2,1},{2,2},{1,2},{-1,2},{-2,2},{-2,1}};//这个偏移量数组推了好久

void dfs(int x,int y,int cnt)
{
	dp[x][y]=cnt;
	for(int i=0;i<12;i++)//这个地方直接裸搜会爆栈,相当于12^20次方 
	{
		xx=x+xy[i][0];
		yy=y+xy[i][1];
		if(xx>=1 && xx<=M && yy>=1 && yy<=M && !mk[xx][yy])//记忆化+最优性剪枝 
		{
			//cout<<"hhh"<<endl;
			if(!dp[xx][yy] || dp[xx][yy]>cnt+1)
			{
				mk[xx][yy]=1;
				dfs(xx,yy,cnt+1);
				mk[xx][yy]=0;
			}
		}
	}
}

int main()
{
	int idx=2;
	while(idx--)
	{
		for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) mk[i][j]=0;
		for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) dp[i][j]=0;
		res=0x3f3f3f3f3f;
		cnt=0; 
		cin>>stx>>sty;
		mk[stx][sty]=1;
		dfs(1,1,0);
		cout<<dp[1][1]<<endl;//走到1,1的最短距离 
	}
	return 0;
}
2024/7/9 16:53
加载中...