結果

問題 No.8063 幅優先探索
ユーザー seven_threeseven_three
提出日時 2020-04-01 21:48:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,159 bytes
コンパイル時間 831 ms
コンパイル使用メモリ 98,920 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 10:24:55
合計ジャッジ時間 2,028 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 RE -
testcase_04 WA -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main(){
	int r, c;
	int s1, s2, g1, g2;
	char m[51][51];
	queue<int> bfs;
	queue<int> bfs1;
	int bfs2[50][50] = { 0 };
	int ans = 0;
	int b1[4] = { 0,0,1,-1 };
	int b2[4] = { 1,-1,0,0 };
	cin >> r >> c >> s1 >> s2 >> g1 >> g2;
	s1--;
	s2--;
	g1--;
	g2--;
	bfs.push(s2);
	bfs1.push(s1);
	for (int a = 0; a < r; a++) {
		for (int b = 0; b < c; b++) {
			cin >> m[b][a];
		}
	}
	for (;;) {
		if (bfs.front() == g2 && bfs1.front() == g1) {
			cout << bfs2[bfs.front()][bfs1.front()] << endl;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			if (m[bfs.front() + b1[i]][bfs1.front() + b2[i]] == '.' && bfs2[bfs.front() + b1[i]][bfs1.front() + b2[i]] == 0) {
				bfs.push(bfs.front() + b1[i]);
				bfs1.push(bfs1.front() + b2[i]);
				bfs2[bfs.front() + b1[i]][bfs1.front() + b2[i]] = bfs2[bfs.front()][bfs1.front()] + 1;
			}
		}
		ans++;
		bfs.pop();
		bfs1.pop();
	}
}
0