Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴一个一般般的代码

Posted by a280920481 at 2018-10-11 21:10:20 on Problem 3009
//我觉得需要注意的是递归的时候要对已经走过10步以上的情况进行剪枝,否则会超时

#include <queue>
#include <iostream>
using namespace std;

struct situ
{
	int x;
	int y;
	int t;
};
const int px[4] = { -1,0,0,1 };
const int py[4] = { 0,-1,1,0 };
int aa[20][20];// 0 - 空地  1 - 障碍  2 - 起点  3 - 终点
int mx = 0, my = 0;//地图大小

void solve(int x, int y, int t);

int nans = 0;
int ansstep = 11;

int main()
{
	int beginx = 0, beginy = 0;
	while (true)
	{
		ansstep = 11;
		nans = 0;
		scanf_s("%d%d", &my, &mx);
		if (mx == 0 || my == 0)
		{
			return 0;
		}
		for (int i = 0; i < mx; i++)
		{
			for (int t = 0; t < my; t++)
			{
				scanf_s("%d", &aa[i][t]);
				if (aa[i][t] == 2)
				{
					beginx = i;
					beginy = t;
				}
			}
		}
		solve(beginx, beginy, 1);

		if (ansstep > 10)
		{
			cout << -1 << endl;
		}
		else
		{		
			printf_s("%d\n", ansstep);
		}

	}

}
void solve(int x, int y, int t)
{
	int lx, ly;
	if (t > 10)
	{
		return;
	}
	for (int i = 0; i < 4; i++)//对于4个方向
	{
		lx = x;
		ly = y;
		while (true)
		{
			lx += px[i];
			ly += py[i];
			if (lx >= 0 && lx < mx && ly >= 0 && ly < my)//没有超界
			{
				if (aa[lx][ly] == 1)//如果前方是障碍
				{
					if (((lx - px[i]) != x) || ((ly - py[i]) != y))
					{
						aa[lx][ly] = 0;
						solve(lx - px[i], ly - py[i], t + 1);
						aa[lx][ly] = 1;//回溯
					}
					break;
				}
				else if (aa[lx][ly] == 3)//如果前方是终点
				{
					if (t < ansstep)
					{
						ansstep = t;
					}
					break;
				}
			}
			else//如果超界则剪枝
			{
				break;
			}
		}

	}
	return;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator