Submission #941219

#	Time	Username	Problem	Language	Result	Execution time	Memory
941219		dsyz	Maze (JOI23_ho_t3)	C++17	8 / 100	69 ms	29248 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll R,C,N;
	cin>>R>>C>>N;
	pair<ll,ll> start, end;
	cin>>start.first>>start.second;
	cin>>end.first>>end.second;
	start.first--, start.second--, end.first--, end.second--;
	char arr[R][C];
	for(ll i = 0;i < R;i++){
		for(ll j = 0;j < C;j++){
			cin>>arr[i][j];
		}
	}
	deque<pair<ll,ll> > dq;
	ll dist[R][C];
	bool visited[R][C];
	memset(dist,0,sizeof(dist));
	memset(visited,0,sizeof(visited));
	int Hy[] = {0,0,-1,1};
	int Wx[] = {-1,1,0,0};
	dq.push_back({start.first,start.second});
	dist[start.first][start.second] = 0;
	visited[start.first][start.second] = 1;
	while(!dq.empty()){
		ll y = dq.front().first;
		ll x = dq.front().second;
		dq.pop_front();
		visited[y][x] = 1;
		for(ll i = 0;i < 4;i++){
			ll a = y + Hy[i];
			ll b = x + Wx[i];
			if(a < 0 || a >= R || b < 0 || b >= C || visited[a][b]) continue;
			if(arr[a][b] == '#'){
				dq.push_back({a,b});
				dist[a][b] = dist[y][x] + 1;
				visited[a][b] = 1;
			}else{
				dq.push_front({a,b});
				dist[a][b] = dist[y][x];
				visited[a][b] = 1;
			}
		}
	}
	cout<<dist[end.first][end.second]<<'\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6