Submission #1046194

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1046194	2024-08-06T11:26:09 Z	lozergam	Maze (JOI23_ho_t3)	C++17	Compilation error	0 ms	0 KB

Main

#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

const ll INF = 1e18;
vector<vector<bool>> a, vis;
arr(2) s, e;
ll n, m, k;
ll ans;
vector<arr(2)> v, g;
vector<set<ll>> row, col;
ll cnt;

void bfs()
{
    // debug(cnt);
	while(!v.empty())
	{
		auto x = v.back();
        // debug(x[0]);
        // debug(x[1]);
		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;
            }
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	
	cin >> n >> m >> k;
	
	a.resize(n + 1);
	vis.resize(n + 1);
	row.resize(n + 1);
	col.resize(m + 1);
	
	For(i, n + 1)
	{
		a[i].resize(m + 1, 0);
		
		vis[i].resize(m + 1, 0);
		
		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;
				
			row[i].insert(j);
			col[j].insert(i);
		}
        
	For(i, n + 1)
		row[i].insert(INF);
	For(i, m + 1)
		col[i].insert(INF);
	
	v.pb(s);
	vis[s[0]][s[1]] = 1;

// 2 4 2
// 1 1
// 2 4
// .###
// ###.

	while(1)
	{
		bfs();
		
		if(vis[e[0]][e[1]])
			break;
		
		for(auto x : g)
		{
			arr(2) r, c;
			
			r[0] = max(x[0] - k + 1, 1ll);
			r[1] = min(x[0] + k - 1, n);
			c[0] = max(x[1] - k + 1, 1ll);
			c[1] = min(x[1] + k - 1, m);
			
			// debug(x[0]);
			// debug(x[1]);
			// debug(r[0]);
			// debug(r[1]);
			// debug(c[0]);
			// debug(c[1]);
			// debug(endl);

			auto it = row[r[0]].lower_bound(c[0]);
			
			while((*it) <= c[1])
			{
				if(!vis[r[0]][(*it)])
				{
					vis[r[0]][(*it)] = 1;
					v.pb({r[0], (*it)});
				}
				
				row[r[0]].erase(it);
				it = row[r[0]].lower_bound(c[0]);
			}
			
			it = row[r[1]].lower_bound(c[0]);
			
			while((*it) <= c[1])
			{
				if(!vis[r[1]][(*it)])
				{
					vis[r[1]][(*it)] = 1;
					v.pb({r[1], (*it)});
				}
				
				row[r[1]].erase(it);
				it = row[r[1]].lower_bound(c[0]);
			}
			
			it = col[c[0]].lower_bound(r[0]);
			
			while((*it) <= r[1])
			{
				if(!vis[(*it)][c[0]])
				{
					vis[(*it)][c[0]] = 1;
					v.pb({(*it), c[0]});
				}
				
				col[c[0]].erase(it);
				it = col[c[0]].lower_bound(r[0]);
			}
			
			it = col[c[1]].lower_bound(r[0]);
			
			while((*it) <= r[1])
			{
				if(!vis[(*it)][c[1]])
				{
					vis[(*it)][c[1]] = 1;
					v.pb({(*it), c[1]});
				}
				
				col[c[1]].erase(it);
				it = col[c[1]].lower_bound(r[0]);
			}
			
			v.pb(x);
			vis[x[0]][x[1]] = 1;
			
			if(e[0] >= r[0] and e[0] <= r[1] and e[1] >= c[0] and e[1] <= c[1])
				vis[e[0]][e[1]] = 1;
		}
		
		g.clear();
		
		ans++;
	}
	
	cout << ans << endl;
}

Compilation message

Main.cpp:14:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll INF = 1e18;
      |                ^~~~
Main.cpp: In function 'int main()':
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:90:2: note: in expansion of macro 'For'
   90 |  For(i, n + 1)
      |  ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:96:3: note: in expansion of macro 'For'
   96 |   For(j, m + 1)
      |   ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:118:2: note: in expansion of macro 'For'
  118 |  For(i, n + 1)
      |  ^~~
Main.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0; (i) < (n); (i)++)
      |                           ^
Main.cpp:120:2: note: in expansion of macro 'For'
  120 |  For(i, m + 1)
      |  ^~~
Main.cpp:143:32: error: no matching function for call to 'max(std::array<int, 2>::value_type, long long int)'
  143 |    r[0] = max(x[0] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:143:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  143 |    r[0] = max(x[0] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:143:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  143 |    r[0] = max(x[0] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:143:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  143 |    r[0] = max(x[0] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:143:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  143 |    r[0] = max(x[0] - k + 1, 1ll);
      |                                ^
Main.cpp:145:32: error: no matching function for call to 'max(std::array<int, 2>::value_type, long long int)'
  145 |    c[0] = max(x[1] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:145:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  145 |    c[0] = max(x[1] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:145:32: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  145 |    c[0] = max(x[1] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:145:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  145 |    c[0] = max(x[1] - k + 1, 1ll);
      |                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:145:32: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  145 |    c[0] = max(x[1] - k + 1, 1ll);
      |                                ^