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

110120_119

Posted by 110120_119 at 2019-03-27 17:35:05 on Problem 3009
#include<cstdio>
#pragma warning (disable:4996)
using namespace std;

int col, row;
int minStep;				//最小步数
int field[110][110];		//存储地图
int direction[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };		//方向

void dfs(int x, int y, int step)
{
	if (step > 10 || step > minStep)
		return;

	for (int i = 0; i < 4; i++)
	{
		int nx = x + direction[i][0];		//先选择一个方向让石头飞
		int ny = y + direction[i][1];
		//printf("xyi: %d %d %d\n", x, y, i);
		while (0 <= nx && nx < row && 0 <= ny && ny < col)	//只要没有越界就让石头一直飞
		{
			//对飞行过程中可能出现的情况做判断
			switch (field[nx][ny])
			{
			case 0:					//空地情况
				nx += direction[i][0];		//朝当前的方向继续飞
				ny += direction[i][1];
				break;
			case 3:					//到达终点
				if (step + 1 < minStep)	//若当前步数小于最小步数,则更新步数
					minStep = step + 1;
				return;
			case 1:					//遇到了石头,分为两种情况,一是:相邻石头(不可以撞碎),二是:飞行过程中遇到石头,则撞碎
				if (!(nx - direction[i][0] == x && ny - direction[i][1] == y))		//若后退一步不是初始位置,说明不是相邻石头
				{
					field[nx][ny] = 0;		//不是相邻石头则将其变成空地
					dfs(nx - direction[i][0], ny - direction[i][1], step + 1); //后退一步,再次深搜,步数加1
					field[nx][ny] = 1;		//刚才的石头需要复原,供下一次尝试
				}
				nx = -1;	//不论是否是相邻石头,只要碰到石头,则需要换方向,此时需要破坏掉while中的条件,使while循环终止,继续进行for循环
				break;
			}
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	int sx, sy;
	while (scanf("%d %d", &col, &row) != EOF)
	{
		if (col == 0 && row == 0)
			return 0;

		minStep = 11;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				scanf("%d", &field[i][j]);
				if (field[i][j] == 2)		//记录开始位置
				{
					sx = i;
					sy = j;
					field[i][j] = 0;		//将开始的点变为空地
				}
			}
		}
		dfs(sx, sy, 0);

		if (minStep > 10)
			minStep = -1;		//步数大于10步则说明不可以到达终点

		printf("%d\n", minStep);	//打印最小步数
	}
	return 0;
}

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