제출 #1052828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1052828		lozergam	Maze (JOI23_ho_t3)	C++17	100 / 100	1046 ms	460592 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#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;
//arr(2) v[6000000], g[6000000];
//ll pv = -1, pg = -1;
//
//int main()
//{
//	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// 	
// 	srand(time(0));
////  	mt19937 mt(3);  
// 
//	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[++pv] = s;
//	vis[s[0]][s[1]] = 1;
// 
//	while(1)
//	{
//		while(pv != -1)
//		{
//			auto x = v[pv];
//			if(x[0] == e[0] and x[1] == e[1])
//				break;
//			pv--;
//			
//			if(x[0] != 1 and !vis[x[0] - 1][x[1]])
//			{
//				if(a[x[0] - 1][x[1]])
//					g[++pg] = {x[0] - 1, x[1]};
//				else
//	            {
//	                vis[x[0] - 1][x[1]] = 1;
//					v[++pv] = {x[0] - 1, x[1]};
//	            }
//			}
//			
//			if(x[0] != n and !vis[x[0] + 1][x[1]])
//			{
//				if(a[x[0] + 1][x[1]])
//					g[++pg] = {x[0] + 1, x[1]};
//				else
//	            {
//					v[++pv] = {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[++pg] = {x[0], x[1] - 1};
//				else
//	            {
//					v[++pv] = {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[++pg] = {x[0], x[1] + 1};
//				else
//	            {
//					v[++pv] = {x[0], x[1] + 1};
//	                vis[x[0]][x[1] + 1] = 1;
//	            }
//			}
//		}
//		
//		if(vis[e[0]][e[1]])
//			break;
//		
//		while(pg >= 0)
//		{
//			arr(2) x = g[pg];
//			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[++pv] = {r[i], c[j]};
//						vis[r[i]][c[j]] = 1;
//					}
//			
//								
//			ll m = 50;
//						
//			if(k != 1)
//			{
//				For(i, m)
//				{
//					long long rn = rand();
//					
//					For(j, 2)
//					{
//						ll t = rn % (c[1] - c[0]) + c[0];
//						if(!vis[r[j]][t])
//						{
//							v[++pv] = {r[j], t};
//							vis[r[j]][t] = 1;
//						}
//					}
//					
//					For(j, 2)
//					{
//						ll t = rn % (r[1] - r[0]) + r[0];
//						if(!vis[t][c[j]])
//						{
//							v[++pv] = {t, c[j]};
//							vis[t][c[j]] = 1;
//						}
//					}
//				}
//			}
//			pg--;
//		}
//		
//		pg = -1;
//		
//		ans++;
//	}
//	
//	cout << ans << endl;
//}
//94/100	\(´~`)/
 
ll r, c, n;
arr(2) s, e;
queue<arr(2)> q[2];
ll ans, o = -1;
vector<vector<char>> a;//its not int!
ll pos;
queue<arr(3)> bfs1, bfs2;
vector<arr(3)> v;
vector<vector<bool>> vis1, vis2, vis3, vis4;

bool check(ll x, ll y, ll z)
{
   	if(x < 0 || y < 0 || x >= c || y >= r) return 1;
   	
    if(a[x][y] == '.')
	{
        q[z%2].push({x, y});
        return 1;
    }
    
    return 0;
};
    
int main(){
    
    cin >> c >> r >> n;
 
    cin >> s[0] >> s[1];
    s[0]--; s[1]--;
    
    cin >> e[0] >> e[1];
    e[0]--; e[1]--;
 
 	a.resize(c);
 	
 	For(i, c)
 	{
 		a[i].resize(r);	
	 	For(j, r)
		 	cin >> a[i][j];	
	}
 	
 
    q[0].push(s);
 
 	
 	vis1.resize(c);
 	vis2.resize(c);
 	vis3.resize(c);
 	vis4.resize(c);
 	
 	For(i, c)
 	{
 		vis1[i].resize(r);
 		vis2[i].resize(r);
 		vis3[i].resize(r);
 		vis4[i].resize(r);
 		
 		For(j, r)
 		{
 			vis1[i][j] = 0;
 			vis2[i][j] = 0;
 			vis3[i][j] = 0;
 			vis4[i][j] = 0;
		 }
	 }
 	
    while(pos < r*c && o == -1)
	{   
        if(q[pos % 2].empty())
		{
            pos++;
 
            while(!bfs1.empty())
			{
                auto [z, x, y] = bfs1.front();
                vis1[x][y] = 0;
                if(z!=0)
                bfs2.push({n, x, y});
                else
                    v.push_back({n-1, x, y});
 
                q[pos%2].push({x, y});
                bfs1.pop();
				    
//                debug(x);
//                debug(y);

                if(z<=0) continue;
 
                if(y - 1 >= 0 and !vis1[x][y - 1] and !vis2[x][y - 1])
				{
                    a[x][y-1] = '.';
                    vis2[x][y-1] = 1;
                    bfs1.push({z-1, x, y-1});
                }
                
                if(y + 1 < r and !vis1[x][y + 1] and !vis2[x][y + 1])
				{
                    a[x][y + 1] = '.';
                    vis2[x][y + 1] = 1;
                    bfs1.push({z - 1, x, y + 1});
                }
            }
 
            while(v.size())
			{
                bfs2.push(v.back());
                v.pop_back();
            }
            
            while(bfs2.size()){
                auto [z, x, y] = bfs2.front();
                vis1[x][y] = 0;
                bfs2.pop();
//                debug(x);
//                debug(y);
//                debug(z);
 
                if(z <= 0) continue;
                if(x - 1 >= 0 and !vis1[x - 1][y] and !vis2[x - 1][y])
				{
                    a[x - 1][y] = '.';
                    vis2[x - 1][y] = 1;
                    bfs2.push({z - 1, x - 1, y});
                }
                
                if(x + 1 < c and !vis1[x + 1][y] and !vis2[x + 1][y])
				{
                    a[x + 1][y] = '.';
                    vis2[x + 1][y] = 1;
                    bfs2.push({z - 1, x + 1, y});
                }
            }
 
            
        }
        else
		{
 
            while(q[pos % 2].size()){
                auto [x, y] = q[pos % 2].front();
                q[pos % 2].pop();
                int ans = 0;
                if(vis1[x][y]) continue;
 
                vis1[x][y] = 1;
                if(x == e[0] and y == e[1] and o == -1)
                    o = pos; 
 
                ans += check(x-1, y, pos);
                ans += check(x+1, y, pos);
                ans += check(x, y-1, pos);
                ans += check(x, y+1, pos);
                
                if(ans != 4)
                    bfs1.push({n, x, y});
            }
        }
 
 
    }
 	
// 	debug(ans);
 	
    cout << o << '\n';
 
} 

컴파일 시 표준 에러 (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:213:3: note: in expansion of macro 'For'
  213 |   For(i, c)
      |   ^~~
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:216:4: note: in expansion of macro 'For'
  216 |    For(j, r)
      |    ^~~
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:229:3: note: in expansion of macro 'For'
  229 |   For(i, c)
      |   ^~~
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:236:4: note: in expansion of macro 'For'
  236 |    For(j, r)
      |    ^~~

• 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: 6 / 6