Advertisement
sashomaga

3d walk

Feb 2nd, 2013
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 6.00 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. //You are given a rectangular cuboid of size W (width), H (height) and D (depth) consisting of W * H * D cubes, each containing an integer number.
  4. //A 3D max walk in the cuboid starts from the cube located at the cuboid's center (W, H and D are odd numbers). At each step the walk continues
  5. //from the current cube in one of the 6 possible directions (left, right, up, down, deeper, shallower) to the cube which holds the maximal
  6. //value among all possible cubes different than the current. The walk stops at some of the following conditions:
  7. //•   Several cubes hold the same maximal value.
  8. //•   There is only cube holding the maximal value but it is already visited (falls into a loop).
  9. //Your task is to write a program that finds the sum of the numbers in the cubes that are visited during the 3D max walk.
  10. class Program
  11. {
  12.     static int result;
  13.  
  14.     static void Main()
  15.     {
  16.         int width; // x
  17.         int height; // y
  18.         int depth; // z
  19.  
  20.         string[] input = Console.ReadLine().Split();
  21.         width = int.Parse(input[0]);
  22.         height = int.Parse(input[1]);
  23.         depth = int.Parse(input[2]);
  24.  
  25.         int[, ,] cube = new int[width, height, depth];
  26.         bool[, ,] visited = new bool[width, height, depth];
  27.  
  28.         string[] rows = new string[height]; // y
  29.         string[] columns = new string[depth]; // z
  30.         string[] cells = new string[width]; // x
  31.         for (int y = 0; y < height; y++)
  32.         {
  33.             rows[y] = Console.ReadLine();
  34.             //rows[0] = "3 4 1 9 1 | 0 1 2 3 8 | 1 2 5 6 7";
  35.             //rows[1] = "2 7 3 1 9 | 2 5 5 2 1 | 8 6 3 5 8";
  36.             //rows[2] = "1 8 2 1 5 | 9 1 3 8 6 | 4 5 6 3 2";
  37.             for (int z = 0; z < depth; z++)
  38.             {
  39.                 columns = rows[y].Split(new string[] { " | " }, StringSplitOptions.None);
  40.                 cells = columns[z].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
  41.                 for (int x = 0; x < width; x++)
  42.                 {
  43.                     cube[x, y, z] = int.Parse(cells[x]);
  44.                 }
  45.  
  46.             }
  47.         }
  48.         //PrintCube(cube);          
  49.  
  50.         CheckPositions(cube, visited, width, height, depth);
  51.  
  52.     }
  53.  
  54.     private static void CheckPositions(int[, ,] cube, bool[, ,] visited, int width, int height, int depth)
  55.     {
  56.         Position current = new Position(width / 2, height / 2, depth / 2);
  57.  
  58.         result += cube[current.x, current.y, current.z];
  59.         visited[current.x, current.y, current.z] = true;
  60.         TryAllPositions(cube, visited, width, height, depth, current);
  61.  
  62.  
  63.     }
  64.  
  65.     private static void TryAllPositions(int[, ,] cube, bool[, ,] visited, int width, int height, int depth, Position current)
  66.     {
  67.  
  68.         List<Position> posiblePositions = new List<Position>();
  69.         if (current.x + 1 < width) // x +
  70.         {
  71.             for (int i = current.x + 1; i < width; i++)
  72.             {
  73.                 posiblePositions.Add(new Position(i, current.y, current.z));
  74.             }
  75.         }
  76.         if (current.x - 1 >= 0) // x -
  77.         {
  78.             for (int i = current.x - 1; i >= 0; i--)
  79.             {
  80.                 posiblePositions.Add(new Position(i, current.y, current.z));
  81.             }
  82.         }
  83.         if (current.y + 1 < height) // y +
  84.         {
  85.             for (int i = current.y + 1; i < height; i++)
  86.             {
  87.                 posiblePositions.Add(new Position(current.x, i, current.z));
  88.             }
  89.         }
  90.         if (current.y - 1 >= 0) // y -
  91.         {
  92.             for (int i = current.y - 1; i >= 0; i--)
  93.             {
  94.                 posiblePositions.Add(new Position(current.x, i, current.z));
  95.             }
  96.         }
  97.         if (current.z + 1 < depth) // z +
  98.         {
  99.             for (int i = current.z + 1; i < depth; i++)
  100.             {
  101.                 posiblePositions.Add(new Position(current.x, current.y, i));
  102.             }
  103.         }
  104.         if (current.z - 1 >= 0) // z -
  105.         {
  106.             for (int i = current.z - 1; i >= 0; i--)
  107.             {
  108.                 posiblePositions.Add(new Position(current.x, current.y, i));
  109.             }
  110.         }
  111.  
  112.         int maxValue = int.MinValue;
  113.         bool isDuplicated = false;
  114.         Position bestPosition = current;
  115.         for (int i = 0; i < posiblePositions.Count; i++)
  116.         {
  117.             if (maxValue == cube[posiblePositions[i].x, posiblePositions[i].y, posiblePositions[i].z])
  118.             {
  119.                 isDuplicated = true;
  120.             }
  121.             if (cube[posiblePositions[i].x, posiblePositions[i].y, posiblePositions[i].z] > maxValue)
  122.             {
  123.                 maxValue = cube[posiblePositions[i].x, posiblePositions[i].y, posiblePositions[i].z];
  124.                 bestPosition = posiblePositions[i];
  125.                 isDuplicated = false;
  126.             }
  127.         }
  128.         if (isDuplicated == false && (visited[bestPosition.x, bestPosition.y, bestPosition.z] == false))
  129.         {
  130.             current = bestPosition;
  131.             result += cube[current.x, current.y, current.z];
  132.             visited[current.x, current.y, current.z] = true;
  133.             TryAllPositions(cube, visited, width, height, depth, current); //recursion
  134.         }
  135.         else
  136.         {
  137.             Console.WriteLine(result);
  138.             Environment.Exit(0);
  139.         }
  140.  
  141.     } //here set breakpoint !!!!!!!
  142.  
  143.     private static void PrintCube(int[, ,] cube)
  144.     {
  145.         for (int y = 0; y < cube.GetLength(1); y++)
  146.         {
  147.  
  148.             for (int z = 0; z < cube.GetLength(2); z++)
  149.             {
  150.  
  151.                 for (int x = 0; x < cube.GetLength(0); x++)
  152.                 {
  153.  
  154.                     Console.Write(cube[x, y, z]);
  155.                 }
  156.                 Console.Write(" ");
  157.             }
  158.             Console.WriteLine();
  159.         }
  160.     }
  161. }
  162.  
  163. class Position
  164. {
  165.     public int x;
  166.     public int y;
  167.     public int z;
  168.  
  169.     public Position(int x, int y, int z)
  170.     {
  171.         this.x = x;
  172.         this.y = y;
  173.         this.z = z;
  174.  
  175.     }
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement