3088401_ac_513ms_45920k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

int w, h;
struct node 
{
	int dir;
	int step;
	int i, j;
	int brd[21][21];
};

queue <node> que;

bool valid(int i,int j)
{
	if (i < 0 || j < 0 || i >= h || j >= w)
	{
		return false;
	}
	return true;
}

void bfs()
{
	node t, q;
	int dir[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
	int opp[] = {1,0,3,2};

	while (!que.empty())
	{
		t = que.front();
		que.pop();
		for (int i = 0; i < 4; i++)
		{
			q = t;
			int x = dir[i][0], y = dir[i][1];
			if (!valid(q.i+x,q.j+y)||q.brd[q.i+x][q.j+y]==1)
			{
				continue;
			}
			while (valid(q.i+x,q.j+y))
			{
				q.i += x;q.j += y;
				if (q.brd[q.i][q.j]==1)
				{
					q.brd[q.i][q.j] = 0;
					q.i -= x;q.j -= y;
					q.dir = i;
					q.step++;
					if (q.step < 10)
					{
						que.push(q);
					}
					break;
				}
				if (q.brd[q.i][q.j]==3)
				{
					q.step++;
					printf("%d\n",q.step);
					return ;
				}
			}
		}
	}
	puts("-1");
}

int main()
{
	while (scanf("%d%d",&w,&h)==2)
	{
		if (w==0&&h==0)
		{
			break;
		}
		while (!que.empty())
		{
			que.pop();
		}
		node t;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				scanf("%d",&t.brd[i][j]);
				if (t.brd[i][j]==2)
				{
					t.i = i;
					t.j = j;
					t.brd[i][j] = 0;
				}
			}
		}
		t.step = 0;
		t.dir = -1;
		que.push(t);
		bfs();
	}
	return 0;
}