Ruudukko

input/code.cpp: In function 'int main()':
input/code.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%i", &d);
      |         ~~~~~^~~~~~~~~~
input/code.cpp:138:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |                         scanf("%i", &grid[i * d + j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_map>
#include <optional>


#define ull unsigned long long int

int d = 0;
std::vector<int> grid;
std::unordered_map<int, ull> cache;

std::optional<ull> getValueAtCache(int loc)
{
	auto found = cache.find(loc);

	if (found != cache.end())
	{
		return std::optional<ull>{found->second};
	}

	else
	{
		return std::nullopt;
	}
}

ull findNumPath(int x, int y)
{

	auto currNum = grid[y * d + x];
	ull nPath = 0;

	for (int i = 1; i < d; i++)
	{
		//test left and right, up and down

		if ((y - i >= 0) && (y - i < d))
		{
			int g = (y - i) * d + x;
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x, y - i);
					cache[g] = a;
					nPath += a;
				}
			}

		}
		if ((y + i >= 0) && (y + i < d))
		{
			int g = (y + i) * d + x;
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x, y + i);
					cache[g] = a;
					nPath += a;
				}
			}
			
		}
		if ((x - i >= 0) && (x - i < d))
		{
			int g = y * d + (x - i);
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x-i, y);
					cache[g] = a;
					nPath += a;
				}
			}
		}
		if ((x + i >= 0) && (x + i < d))
		{
			int g = y * d + (x + i);
			auto gn = grid[g];
			if (gn < currNum)
			{
				nPath++;
				auto v = getValueAtCache(g);
				if (v.has_value())
				{
					nPath += v.value();
				}
				else
				{
					auto a = findNumPath(x + i, y);
					cache[g] = a;
					nPath += a;
				}
			}
		}

	}
	return nPath;

}


int main()
{
	scanf("%i", &d);
	grid.resize(d * d);
	cache.reserve(d * d);
	for (int i = 0; i < d; i++)
	{
		for (int j = 0; j < d; j++)
		{
			//x is row j is column
			scanf("%i", &grid[i * d + j]);
		}
	}

	ull nPath = 0;
	for (int i = 0; i < d; i++)
	{
		for (int j = 0; j < d; j++)
		{
			nPath += (findNumPath(i, j) + 1);
		}
	}
	auto n = nPath % 1000000007;
	printf("%llu", n );


}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: WRONG ANSWER

Test 6

Group: 2, 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED