Task
The Goal
The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.
The goal is to find, when they exist, the horizontal and vertical neighbors of each node.
Rules
To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.
If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].
You lose if:
- You give an incorrect neighbor for a node.
- You give the neighbors for an empty cell.
- You compute the same node twice.
- You forget to compute the neighbors of a node.
Game input
The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.
Initialization input
Line 1: one integer width for the number of cells along the x axis.
Line 2: one integer height for the number of cells along the y axis.
Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.
[latex]0 <[/latex] width[latex]\le 30[/latex][latex]0 <[/latex] height[latex]\le 30[/latex]
Output for one game turn
One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:
- ( x1, y1) the coordinates of a node.
- ( x2, y2) the coordinates the closest neighbor on the right of the node.
- ( x3, y3) the coordinates the closest bottom neighbor.
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.
Tests
| Input | Output |
|---|---|
| 2 2 00 0. |
0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1 |
| 4 4 .0.. .000 000. ..0. |
1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1 |
The code of the program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <string> using namespace std; int main() { short width; // the number of cells on the X axis cin >> width; cin.ignore(); short height; // the number of cells on the Y axis cin >> height; cin.ignore(); string *node = new string[height]; short x, y; for (y = 0; y < height; ++y) { getline(cin, node[y]); } for (y = 0; y < height; ++y) { for (x = 0; x < width; ++x) { if (node[y][x] == '0') { cout << x << ' ' << y << ' '; short x2, y2, ansX = -1, ansY = -1; for (x2 = x+1; x2 < width; ++x2) { if (node[y][x2] == '0') { ansX = x2; ansY = y; break; } } cout << ansX << ' ' << ansY << ' '; ansX = -1; ansY = -1; for (y2 = y+1; y2 < height; ++y2) { if (node[y2][x] == '0') { ansX = x; ansY = y2; break; } } cout << ansX << ' ' << ansY << '\n'; x = x2-1; } } } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.*; import java.io.*; import java.math.*; class Player { public static void main(String args[]) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); short width = in.nextShort(); // the number of cells on the X axis short height = in.nextShort(); // the number of cells on the Y axis if (in.hasNextLine()) { in.nextLine(); } String node[] = new String[height]; for(short y = 0; y < height; ++y) { node[y] = in.nextLine(); } for(short y = 0; y < height; ++y) { for(short x = 0; x < width; ++x) { if (node[y].charAt(x) == '0') { out.printf(String.valueOf(x)+" "+String.valueOf(y)+" "); short x2, y2, ansX = -1, ansY = -1; for (x2 = (short)(x+1); x2 < width; ++x2) { if (node[y].charAt(x2) == '0') { ansX = x2; ansY = y; break; } } out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" "); ansX = -1; ansY = -1; for(y2 = (short)(y+1); y2 < height; ++y2) { if (node[y2].charAt(x) == '0') { ansX = x; ansY = y2; break; } } out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n"); x = (short)(x2-1); } } } out.flush(); } } |
Solution of the task
First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.
After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.
This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.