Submission #1046955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046955		lozergam	Maze (JOI23_ho_t3)	C++17	94 / 100	2074 ms	47808 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll int
#define pb push_back
#define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define sz(x) (ll)x.size()
#define arr(x) array<ll, x>
#define insert emplace

arr(2) s, e;
ll n, m, k;
ll ans;
vector<arr(2)> v, g;
 
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  	mt19937 mt(time(nullptr));  

	cin >> n >> m >> k;
	
	bool a[n + 1][m + 1], vis[n + 1][m + 1];
	
	For(i, n + 1)
		For(j, m + 1)
			vis[i][j] = 0;
	
	cin >> s[0] >> s[1];
	cin >> e[0] >> e[1];
	
	for(int i = 1;i <= n; i++)
		for(int j = 1;j <= m; j++)
		{
			char c;
			cin >> c;
			
			if(c == '.')
				a[i][j] = 0;
			else 
				a[i][j] = 1;
		}
	
	v.pb(s);
	vis[s[0]][s[1]] = 1;
 
	while(1)
	{
		while(!v.empty())
		{
			auto x = v.back();
			v.pop_back();
			
			if(x[0] != 1 and !vis[x[0] - 1][x[1]])
			{
				if(a[x[0] - 1][x[1]])
					g.pb({x[0] - 1, x[1]});
				else
	            {
	                vis[x[0] - 1][x[1]] = 1;
					v.pb({x[0] - 1, x[1]});
	            }
			}
			
			if(x[0] != n and !vis[x[0] + 1][x[1]])
			{
				if(a[x[0] + 1][x[1]])
					g.pb({x[0] + 1, x[1]});
				else
	            {
					v.pb({x[0] + 1, x[1]});
	                vis[x[0] + 1][x[1]] = 1;
	            }
			}
			
			if(x[1] != 1 and !vis[x[0]][x[1] - 1])
			{
				if(a[x[0]][x[1] - 1])
					g.pb({x[0], x[1] - 1});
				else
	            {
					v.pb({x[0], x[1] - 1});
	                vis[x[0]][x[1] - 1] = 1;
	            }
			}
			
			if(x[1] != m and !vis[x[0]][x[1] + 1])
			{
				if(a[x[0]][x[1] + 1])
					g.pb({x[0], x[1] + 1});
				else
	            {
					v.pb({x[0], x[1] + 1});
	                vis[x[0]][x[1] + 1] = 1;
	            }
			}
		}
		
		if(vis[e[0]][e[1]])
			break;
		
		for(auto x : g)
		{
			arr(2) r, c;
			
			r[0] = max(x[0] - k + 1, 1);
			r[1] = min(x[0] + k - 1, n);
			c[0] = max(x[1] - k + 1, 1);
			c[1] = min(x[1] + k - 1, m);

			if(e[0] >= r[0] and e[0] <= r[1] and e[1] >= c[0] and e[1] <= c[1])
			{
				cout << ans + 1 << endl;
				return 0;
			}
			
			For(i, 2)
				For(j, 2)
					if(!vis[r[i]][c[j]])
					{
						v.pb({r[i], c[j]});
						vis[r[i]][c[j]] = 1;
					}
			
								
			ll m = 130;
						
			if(k != 1)
			{
				For(i, m)
				{
					long long rn = mt();
					ll t = rn % (c[1] - c[0]) + c[0];
					For(j, 2)
						if(!vis[r[j]][t])
						{
							v.pb({r[j], t});
							vis[r[j]][t] = 1;
						}
				
					t = rn % (r[1] - r[0]) + r[0];
					For(j, 2)
						if(!vis[t][c[j]])
						{
							v.pb({t, c[j]});
							vis[t][c[j]] = 1;
						}
				}
			}
		}
		
		g.clear();
		
		ans++;
	}
	
	cout << ans << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:31:2: note: in expansion of macro 'For'
   31 |  For(i, n + 1)
      |  ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:32:3: note: in expansion of macro 'For'
   32 |   For(j, m + 1)
      |   ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:123:4: note: in expansion of macro 'For'
  123 |    For(i, 2)
      |    ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:124:5: note: in expansion of macro 'For'
  124 |     For(j, 2)
      |     ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:136:5: note: in expansion of macro 'For'
  136 |     For(i, m)
      |     ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:140:6: note: in expansion of macro 'For'
  140 |      For(j, 2)
      |      ^~~
Main.cpp:9:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:148:6: note: in expansion of macro 'For'
  148 |      For(j, 2)
      |      ^~~

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