Demo entry 6658414

big

   

Submitted by yyl on Nov 07, 2017 at 01:26
Language: C++. Code size: 1.6 kB.

#include<cstdio>
#include<cmath>
#include<queue>
#include <algorithm>
#include <string>
using namespace std;
typedef struct step {
	int x;
	int y;
	int num;
}step;
int map[7][10] = {
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
	{ 1, 1, 1, 0, 1, 1, 0, 0, 1, 1 },
	{ 1, 1, 0, 1, 1, 0, 0, 1, 1, 1 },
	{ 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
	{ 1, 1, 0, 0, 0, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};
int valid(step sat)
{
	if (sat.x < 0 || sat.y <0  || sat.x >= 7 || sat.y >= 10) {
		return 1;
	}
	if (map[sat.x][sat.y] == 1)
	{
		return 1;
	}
	return 0;
}

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int dbx[4] = { 1,-1,-1,1 };
int dby[4] = { 1,1,-1,-1 };
void bfs(step tmp)
{
	queue<step> q;
	q.push(tmp);
	step p;
	while (!q.empty())
	{
		p = q.front();
		q.pop();
		map[p.x][p.y] = 1;
		int flag = 0;
		for (int i = 0; i < 4; i++)
		{
			step next;
			next.x = p.x + dx[i];
			next.y = p.y + dy[i];
			if (valid(next)==0) {
				next.num = p.num + 1;
				map[next.x][next.y] = 1;
				q.push(next);
				flag = 1;
				if (next.x == 1 && next.y == 7)
				{
					printf("最短路径:%d\n", next.num);
				}
			}
		}
		if (flag == 0)
		{
			for (int i = 0; i < 4; i++)
			{
				step next;
				next.x = p.x + dbx[i];
				next.y = p.y + dby[i];
				if (valid(next) == 0) {
					next.num = p.num + 1;
					map[next.x][next.y] = 1;
					q.push(next);
					if (next.x == 1 && next.y == 7)
					{
						printf("最短路径:%d\n", next.num);
					}
				}
			}
		}
	}
}
int main()
{
	step start = { 1,3,0 };
	bfs(start);
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).