Submission #1071381


Source Code Expand

#include "bits/stdc++.h"

#define REP(i,n) for(int i=0;i<n;++i)
#define RREP(i,n) for(int i=n-1;i>=0;--i)
#define FOR(i,m,n) for(int i=m;i<n;++i)
#define RFOR(i,m,n) for(int i=n-1;i>=m;--i)
#define ALL(v) v.begin(),v.end()
#define PB(a) push_back(a)
#define INF 1000000001
#define MOD 1000000007
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

using namespace std;


vector<string > v(50);
vector<vector<int>> val(50, vector<int>(50, -1));
int r, c, sy, sx, gy, gx;
queue<pair<int,int>> q;
void bfs(vector<string>& v,int y, int x) {
	int nx, ny;
	REP(i, 4) {
		nx = x + dx[i * 2];ny = y + dy[i * 2];
		if (ny >= 0 && ny < r&&nx >= 0 && nx < c&&val[ny][nx] == -1 && v[ny][nx] == '.') {
			val[ny][nx] = val[y][x] + 1;
			q.push({ ny,nx });
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> r >> c >> sy >> sx >> gy >> gx;
	REP(i, r) {
		string s;
		cin >> v[i];
	}
	sy--;sx--;gx--;gy--;
	q.push({ sy,sx });
	val[sy][sx] = 0;
	while (!q.empty()) {
		int y = q.front().first, x = q.front().second;
		q.pop();
		bfs(v, y, x);
	}
	cout << val[gy][gx] << endl;
	return 0;
}

Submission Info

Submission Time
Task C - 幅優先探索
User etonagisa
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1202 Byte
Status AC
Exec Time 21 ms
Memory 1048 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All 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
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 19 ms 1044 KB
subtask0_sample02.txt AC 18 ms 1044 KB
subtask0_sample03.txt AC 19 ms 956 KB
subtask1_01.txt AC 20 ms 1048 KB
subtask1_02.txt AC 20 ms 1048 KB
subtask1_03.txt AC 21 ms 920 KB
subtask1_04.txt AC 21 ms 1044 KB
subtask1_05.txt AC 20 ms 920 KB
subtask1_06.txt AC 20 ms 1044 KB
subtask1_07.txt AC 19 ms 1048 KB
subtask1_08.txt AC 20 ms 1048 KB
subtask1_09.txt AC 20 ms 920 KB
subtask1_10.txt AC 18 ms 1048 KB
subtask1_11.txt AC 20 ms 1048 KB
subtask1_12.txt AC 20 ms 1040 KB
subtask1_13.txt AC 20 ms 920 KB
subtask1_14.txt AC 18 ms 1044 KB
subtask1_15.txt AC 18 ms 1040 KB
subtask1_16.txt AC 20 ms 920 KB
subtask1_17.txt AC 20 ms 924 KB
subtask1_18.txt AC 20 ms 1048 KB
subtask1_19.txt AC 20 ms 1048 KB
subtask1_20.txt AC 20 ms 916 KB
subtask1_21.txt AC 20 ms 920 KB
subtask1_22.txt AC 21 ms 1048 KB