AtCoder Beginner Contest 007

Submission #1677060

Source codeソースコード

#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

Task問題 C - 幅優先探索
User nameユーザ名 tsutaya
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2235 Byte
File nameファイル名
Exec time実行時間 1 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
All 100 / 100 subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask1_20.txt AC 1 ms 256 KB
subtask1_21.txt AC 1 ms 256 KB
subtask1_22.txt AC 1 ms 256 KB