Submission #1677060

---

Source Code Expand

#include <iostream>

using namespace std;

struct queue
{
	int y[10000];
	int x[10000];
	int left;
	int right;
};

void init(queue* q)
{
	q->left = -1;
	q->right = 0;
}

void dequeue(queue* q,int a[])
{
	q->right = q->right + 1;
	a[0] = q->y[q->right - 1];
	a[1] = q->x[q->right - 1];
}

void enqueue(queue* q, int y, int x)
{
	q->left = q->left + 1;
	q->y[q->left] = y;
	q->x[q->left] = x;	
}

int main()
{
	int r, c;
	cin >> r >> c;
	
	int sy, sx, gy ,gx;
	cin >> sy >> sx >> gy >> gx;
	
	char map[r][c];
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> map[i][j];
		}
	}

	
	int map_num[r][c];
	bool map_flag[r][c];
	
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			map_flag[i][j] = false;
			map_num[i][j] = 0;;
		}
	}

	queue q;
	
	init(&q);
	
	int zahyou[2];
	
	map_flag[sy - 1][sx - 1] = true;
	enqueue(&q, sy - 1, sx - 1);
	
	int number = 1;
	int rep = 1;
	
	while(map_num[gy - 1][gx - 1] == 0)
	{
		int cnt = 0;
		for (int i = 0; i < rep; i++)
		{
			dequeue(&q, zahyou);
			
			if (map[zahyou[0]][zahyou[1] - 1] == '.' && map_flag[zahyou[0]][zahyou[1] - 1] == false)
			{
				cnt++;
				map_num[zahyou[0]][zahyou[1] - 1] = number;
				map_flag[zahyou[0]][zahyou[1] - 1] = true;
				enqueue(&q, zahyou[0], zahyou[1] - 1);
			}

			if (map[zahyou[0]][zahyou[1] + 1] == '.' && map_flag[zahyou[0]][zahyou[1] + 1] == false)
			{
				cnt++;
				map_num[zahyou[0]][zahyou[1] + 1] = number;
				map_flag[zahyou[0]][zahyou[1] + 1] = true;
				enqueue(&q, zahyou[0], zahyou[1] + 1);
			}

			if (map[zahyou[0] - 1][zahyou[1]] == '.' && map_flag[zahyou[0] - 1][zahyou[1]] == false)
			{
				cnt++;
				map_flag[zahyou[0] - 1][zahyou[1]] = true;
				map_num[zahyou[0] - 1][zahyou[1]] = number;
				enqueue(&q, zahyou[0] - 1, zahyou[1]);
			}

			if (map[zahyou[0] + 1][zahyou[1]] == '.' && map_flag[zahyou[0] + 1][zahyou[1]] == false)
			{
				cnt++;
				map_flag[zahyou[0] + 1][zahyou[1]] = true;
				map_num[zahyou[0] + 1][zahyou[1]] = number;
				enqueue(&q, zahyou[0] + 1, zahyou[1]);
			}
		}
		rep = cnt;
		number++;
	}
	
	cout << map_num[gy - 1][gx - 1] << endl;
}

Submission Info

Judge Result