Table of Contents

ExplanationImplementation

Explanation

We can simulate the spiral around each starting position. For every cell in our solution we will choose the minimum number that visit this cell.

Implementation

Time Complexity: O(K∗N∗M)\mathcal{O}(K*N*M)

C++

#include <bits/stdc++.h>
using namespace std;


vector<int> ux = {0, -1, 0, 1}, uy = {1, 0, -1, 0}, dx = {0, -1, 0, 1},
            dy = {-1, 0, 1, 0};


const int MAX_N = 50;
int mat[MAX_N][MAX_N], num_visited = 0, n, m, k, current_distance = 0;


void update_distance(int x, int y) {

Java

import java.util.*;


public class Spirale {
	static final int MAX_N = 50;
	static int[][] mat = new int[MAX_N][MAX_N];
	static int n, m, k, currentDistance, numVisited;


	static int[] ux = {0, -1, 0, 1};
	static int[] uy = {1, 0, -1, 0};
	static int[] dx = {0, -1, 0, 1};

Python

ux = [0, -1, 0, 1]
uy = [1, 0, -1, 0]
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]


MAX_N = 50
mat = [[(float("inf"))] * MAX_N for _ in range(MAX_N)]
current_distance = 0
num_visited = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum