Submission #1121724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121724		stefanneagu	Maze (JOI23_ho_t3)	C++17	51 / 100	2082 ms	200760 KiB

Main

    #include <bits/stdc++.h>
     
    using namespace std;
     
    int dx[] = {1, -1, 0,  0};
    int dy[] = {0, 0,  -1, 1};
     
    vector<vector<char>> v;
    vector<vector<int>> dp;
    vector<set<int>> s;
    queue<pair<int, int>> q;
     
    int f[101][101];
     
    void flood_fill(int i, int j, int val) {
    	for(int d = 0; d < 4; d++) {
    		int a = i + dx[d];
    		int b = j + dy[d];
    		if(v[a][b] == '.' && s[a].find(b) != s[a].end()) {
    			q.push({a, b});
    			s[a].erase(b);
    			dp[a][b] = val;
    			flood_fill(a, b, val);
    		}
    	}
    }
     
    int32_t main() {
      ios_base::sync_with_stdio(false);
      cin.tie();
      cout.tie();
      int n, m, d;
      cin >> n >> m >> d;
      v.resize(n + 2, vector<char>(m + 2));
      dp.resize(n + 2, vector<int>(m + 2));
      s.resize(n + 2);
      int si, sj, ei, ej;
    	cin >> si >> sj >> ei >> ej;
      for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= m; j++) {
    			cin >> v[i][j];
    			s[i].insert(j);
    			dp[i][j] = 1e9;
    		}
    	}
    	dp[si][sj] = 0;
    	s[si].erase(sj);
    	q.push({si, sj});
    	flood_fill(si, sj, 0);
    	while(!q.empty()) {
    		auto [a, b] = q.front();
    		q.pop();
    		if(a == ei && b == ej) {
    			cout << dp[a][b];
    			return 0;
    		}
    		// deci mergem (a - d, b - d) -> (a + d, b + d) 
    		// fara colturi
    		int p1 = b - d, p2 = b + d, aux;
    		for(int i = max(1, a - d); i <= min(n, a + d); i++) {
    			if(i == a - d || i == a + d) {
    				p1++, p2--;
    			}
    			auto it = s[i].lower_bound(p1);
    			vector<int> de;
    			while(it != s[i].end() && *it <= p2) {
    				aux = *it;
    				dp[i][aux] = dp[a][b] + 1;
    				q.push({i, aux});
    				if((i == a - d || i == a + d || aux == b + d || aux == b - d) && (v[i][aux] == '.' || v[i][aux - 1] == '.' || v[i - 1][aux] == '.'|| v[i][aux + 1] == '.' || v[i + 1][aux] == '.')) {
    					de.push_back(aux);
    				}
    				it++;
    				s[i].erase(aux);
    			}
    			for(auto ip : de) {
    				for(int dir = 0; dir < 4; dir++) {
    					int ii = i + dx[dir];
    					int jj = ip + dy[dir];
    					if(v[ii][jj] == '.' && s[ii].find(jj) != s[ii].end()) {
    						// continue;
    						s[ii].erase(jj);
    						dp[ii][jj] = dp[i][ip];
    						q.push({ii, jj});
    						flood_fill(ii, jj, dp[ii][jj]);
    					}
    				}
    				if(v[i][ip] == '.' && s[i].find(ip) != s[i].end()) {
    					s[i].erase(ip);
    					flood_fill(i, ip, dp[i][ip]);
    				}
    			}
    			if(i == a - d || i == a + d) {
    				p1--, p2++;
    			}
    		}
    	}
    	assert(0);
      return 0;
    }

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