三星研究院真题

由于要参加三星研究院（已通过技术面，人事面）的机试（主要考察DFS,BFS搜索算法，c++只能使用iostream头文件），萌新上路。

题目大意：在二维平面（x，y表示）（0<=x,y<=1000）上，给出起点终点坐标，在平面上存在N个虫洞（0<=N<=5）,每个虫洞有两个出口，进入虫洞经过一段时间后到达另一个出口。求起点到终点的最短时间。注意：到达虫洞所在坐标可以选择进入或不进入，两点间时间计算公式为time=y2-y1+x2-x1,不能斜着走。

input
5           //表示5个测试样例
0           //表示第一组测试样例有0个虫洞
0 0 60 60 //起点(0,0),终点（60,60）
1             //表示第2组测试样例有1个虫洞
0 0 2 0    //起点(0,0),终点（2,0）
1 0 1 2 0  //虫洞两个出口(1,0),终点（1,2），通过虫洞的时间为0
1
0 0 60 60
40 40 20 20 10
2
100 50 10 5
80 40 10 6 10
80 10 70 40 5
3
500 500 1000 1000 
501 501 999 999 1000
1 1 499 499 100
1000 999 0 0 200

output
#1 120
#2 2
#3 90
#4 41
#5 305

遇到的坑：第一次按照一步一步走的方式设计的dfs，妥妥堆栈溢出，后来改变思路dfs方向为走虫洞or直接走。

#include 
using namespace std;
struct MyStruct
{
	int x[2];
	int y[2];
	int cross_time;
};//0<=x,y<=1000
MyStruct wormhole[5];

int start_x, start_y, end_x, end_y, final_time, N;
int visit[5], map[1000][1000];
void dfs(int now_x, int now_y, int time) {
	for (int i = 0; i < N + 1; i++)
	{


		if (time >= final_time && final_time != 0)	return;

		if (now_x == end_x && now_y == end_y)
		{
			if (time < final_time || final_time == 0)
			{
				final_time = time;
			}
			return;
		}//递归开关
		if (visit[i] == 1)
		{
			continue;
		}//虫洞重走剪枝
		if (i != N)
		{
			for (int j = 0; j < 2; j++)
			{
				int a_time;//到达虫洞所需时间
				a_time = abs(wormhole[i].x[j] - now_x) + abs(wormhole[i].y[j] - now_y);
				visit[i] = 1;
				dfs(wormhole[i].x[!j], wormhole[i].y[!j], time + a_time + wormhole[i].cross_time);
				visit[i] = 0;
			}
		}

		else
		{
			int direct_time = abs(end_x - now_x) + abs(end_y - now_y);//直接走的时间
			dfs(end_x, end_y, time + direct_time);
		}



	}


}
void init() {
	memset(wormhole, 0, sizeof(wormhole) * 5);
	memset(visit, 0, sizeof(visit));
	memset(map, -1, sizeof(map));
	final_time = 0;
}
int main()
{
	int T = 0;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		init();
		cin >> N;
		cin >> start_x >> start_y >> end_x >> end_y;
		for (int j = 0; j < N; j++)
		{

			cin >> wormhole[j].x[0] >> wormhole[j].y[0] >> wormhole[j].x[1] >> wormhole[j].y[1]
				>> wormhole[j].cross_time;
		}
		dfs(start_x, start_y, 0);
		cout << "#" << i + 1 << " " << final_time << endl;

	}




}