Submission #1085513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085513		I_am_Polish_Girl	Maze (JOI23_ho_t3)	C++14	51 / 100	2083 ms	205332 KiB

Main

#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 21;
int inf = 4000000007000000007;

long long mod = 998244353;

int p = 499;

int NADIYA = 39;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	int i_st, j_st;
	cin >> i_st >> j_st;

	i_st--;
	j_st--;

	int i_f, j_f;
	cin >> i_f >> j_f;

	i_f--;
	j_f--;


	vector <vector <int>> deep(n);
	vector <vector <int>> t(n);

	for (int i = 0; i < n; i++)
	{
		deep[i].resize(m , inf);
		t[i].resize(m, false);
	}

	vector <string> vs(n);
	for (int i = 0; i < n; i++)
		cin >> vs[i];
	

	vector <vector < pair <int, int>>> q(n*m+2);

	q[0].push_back({i_st , j_st});
	deep[i_st][j_st] = 0;

	vector <pair <int, int>> go;

	go.push_back({ 1 , 0 });
	go.push_back({ -1 , 0 });
	go.push_back({ 0 , 1 });
	go.push_back({ 0 , -1 });


	vector <pair <int, int>> go2;

	for (int i = -n; i <= n; i++)
	{
		for (int j = -n; j <= n; j++)
		{
			go2.push_back({ i , j });
		}
	}
	


	for (int d = 0 ; d < n*m+1  ; d++)
	{
		if (q[d].size() == 0)
			break;

		for (int ind = 0; ind < q[d].size(); ind++)
		{
			int i_ = q[d][ind].first;
			int j_ = q[d][ind].second;


			for (int i = 0; i < 4; i++)
			{
				int i__ = i_ + go[i].first;
				int j__ = j_ + go[i].second;

				if ((i__ >= 0) and (i__ < n))
				{
					if ((j__ >= 0) and (j__ < m))
					{
						if (deep[i__][j__] > d)
						{
							if (vs[i__][j__] == '.')
							{
								deep[i__][j__] = d;
								q[d].push_back({i__ , j__});
							}
						}
					}
				}
			}
		}

		for (int ind = 0; ind < q[d].size(); ind++)
		{
			int i_ = q[d][ind].first;
			int j_ = q[d][ind].second;

			for (int i = -k; i <= k; i++)
			{
				for (int j = -k; j <= k; j += 2 * k)
				{
					if (abs(i) + abs(j) == 2 * k)
						continue;

					int i__ = i_ + i;
					int j__ = j_ + j;

					if ((i__ >= 0) and (i__ < n))
					{
						if ((j__ >= 0) and (j__ < m))
						{
							if (deep[i__][j__] == inf)
							{
								deep[i__][j__] = d + 1;
								q[d+1].push_back({i__ , j__});
							}
						}
					}
				}
			}


			for (int i = -k ; i <= k ; i += 2*k)
			{
				for (int j = -k; j <= k; j ++)
				{
					if (abs(i) + abs(j) == 2 * k)
						continue;

					int i__ = i_ + i;
					int j__ = j_ + j;

					if ((i__ >= 0) and (i__ < n))
					{
						if ((j__ >= 0) and (j__ < m))
						{
							if (deep[i__][j__] == inf)
							{
								deep[i__][j__] = d + 1;
								q[d + 1].push_back({ i__ , j__ });
							}
						}
					}
				}
			}
		}	
	}


	//cout << deep[i_f][j_f] << "\n";

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (abs(i - i_f) <= k)
			{
				if (abs(j - j_f) <= k)
				{
					if ((abs(i - i_f) + abs(j - j_f)) != 2 * k)
					{
						deep[i_f][j_f] = min(deep[i_f][j_f], deep[i][j] + 1);
					}
				}
			}
		}
	}

	cout << deep[i_f][j_f];
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      | 
Main.cpp: In function 'int main()':
Main.cpp:100:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (int ind = 0; ind < q[d].size(); ind++)
      |                     ~~~~^~~~~~~~~~~~~
Main.cpp:128:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for (int ind = 0; ind < q[d].size(); ind++)
      |                     ~~~~^~~~~~~~~~~~~

• 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