AtCoder Beginner Contest 007

Submission #1707015

Source codeソースコード

#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;
using ll = long long;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	int R, C, sy, sx, gy, gx, i, j, d[51][51], y ,x;
	string c[51];
	queue<int> qy, qx;

	for (i = 0; i < 51; i++) {
		for (j = 0; j < 51; j++) {
			d[i][j] = INF;
		}
	}

	cin >> R >> C;
	cin >> sy >> sx;
	d[sy - 1][sx - 1] = 0;
	qy.push(sy - 1);
	qx.push(sx - 1);
	cin >> gy >> gx;
	for (i = 0; i < R; i++) {
		cin >> c[i];
	}

	while (1){
		y = qy.front();
		qy.pop();
		x = qx.front();
		qx.pop();

		if (y == gy - 1 && x == gx - 1) {
			cout << d[y][x] << endl;
			return 0;
		}

		if (y > 0) {
			if (d[y - 1][x] == INF && c[y - 1][x] == '.') {
				d[y - 1][x] = d[y][x] + 1;
				qy.push(y - 1);
				qx.push(x);
			}
		}
		if (x > 0) {
			if (d[y][x - 1] == INF && c[y][x - 1] == '.') {
				d[y][x - 1] = d[y][x] + 1;
				qy.push(y);
				qx.push(x - 1);
			}
		}
		if (y < R - 1) {
			if (d[y + 1][x] == INF && c[y + 1][x] == '.') {
				d[y + 1][x] = d[y][x] + 1;
				qy.push(y + 1);
				qx.push(x);
			}
		}
		if (x < C - 1) {
			if (d[y][x + 1] == INF && c[y][x + 1] == '.') {
				d[y][x + 1] = d[y][x] + 1;
				qy.push(y);
				qx.push(x + 1);
			}
		}
	}
}

Submission

Task問題 C - 幅優先探索
User nameユーザ名 chocobo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1517 Byte
File nameファイル名
Exec time実行時間 2 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 2 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 2 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