Horse-racing Duals

---

The Goal

Casablanca’s hippodrome is organizing a new type of horse racing: duals. During a dual, only two horses will participate in the race. In order for the race to be interesting, it is necessary to try to select two horses with similar strength.

Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer (≥ 0).

Game Input

Input
Line 1: Number N of horses

The N following lines: the strength Pi of each horse. Pi is an integer.

Output

The difference D between the two closest strengths. D is an integer greater than or equal to 0.

Constraints
1 < N < 100000
0 < Pi ≤ 10000000

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
int main()
{
    int N;
    cin >> N; cin.ignore();
    int delta = 10000000;
    int oPi=0;
    int P;
    vector<int> vP;
    for (int i = 0; i < N; i++) {
        int Pi;
        cin >> Pi; cin.ignore();
        vP.push_back(Pi);        
    }    
    sort(vP.begin(),vP.end());
    for(int p:vP){
        P=abs(p-oPi);        
        oPi = p;
        delta = (P < delta)?P:delta;
            
    }

    // Write an action using cout. DON'T FORGET THE "<< endl"
    // To debug: cerr << "Debug messages..." << endl;

    cout << delta << endl;
}

The Goal

Once teleported inside the structure, your mission is to: find the control room from which you will be able to deactivate the tracker beam get back to your starting position once you've deactivated the tracker beam

Rules

The structure is arranged as a rectangular maze composed of cells. Within the maze Kirk can go in any of the following directions: UP, DOWN, LEFT or RIGHT.

Kirk is using his tricorder to scan the area around him but due to a disruptor field, he is only able to scan the cells located in a 5-cell wide square centered on him.

Unfortunately, Spock was correct, there is a trap! Once you reach the control room an alarm countdown is triggered and you have only a limited number of rounds before the alarm goes off. Once the alarm goes off, Kirk is doomed...

Kirk will die if any of the following happens: Kirk's jetpack runs out of fuel. You have enough fuel for 1200 movements. Kirk does not reach the starting position before the alarm goes off. The alarm countdown is triggered once the control room has been reached.
Kirk touches a wall or the ground: he is ripped apart by a mechanical trap. You will be successful if you reach the control room and get back to the starting position before the alarm goes off.

Maze format

A maze in ASCII format is provided as input. The character # represents a wall, the letter . represents a hollow space, the letter T represents your starting position, the letter C represents the control room and the character ? represents a cell that you have not scanned yet. For example:

??????????????????????????????
#..............???????????????
#.#############???????????????
#.....T........???????????????
#.......................#.#..#
#.#######################.#..#
#.....##......##......#....###
#...####..##..##..##..#..#...#
#.........##......##.....#.C.#
##############################

Starting position is at row 3, column 6.

Control room is at row 8, column 27. (Indexes start at zero)

Note

The tests provided are similar to the validation tests used to compute the final score but remain different.

Game Input

The program must first read the initialization data from standard input. Then, within an infinite loop, read the data from the standard input related to the maze's current state and provide to the standard output the next movement instruction.
Initialization input

Line 1: 3 integers: R C A
R,C are the numbers of rows and columns of the maze.
A, is the number of rounds between the time the alarm countdown is activated and the time the alarm goes off.

Input for one game turn
Line 1: 2 integers: KR and KC. Kirk is located at row KR and column KC within the maze. The cell at row 0 and column 0 is located in the top left corner of the maze.

Next R lines: C characters # or . or T or C or ? (i.e. one line of the ASCII maze)

Output for one game turn
A single line containing one of: UP DOWN LEFT or RIGHT

Constraints
10 <= R <= 100
20 <= C <= 200
1 <= A <= 100
0 <= KR < R
0 <= KC < C

Response time per turn <= 150ms

There at a single T character and a single C character within a maze

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <ostream>
#include <climits>
#include <cmath>
#include <deque>
#include <tuple>


using namespace std;
vector<vector<char>> maze;
int width, height;
struct MOVE{
	string out;
	int x;
	int y;	
};

vector<MOVE> moves={{"RIGHT",1,0},{"UP",0,-1},{"LEFT",-1,0}, {"DOWN",0,1}};

enum {FIND_CROOM, FIND_TELEPORT};

enum {E_NA='?', E_WALL='#', E_VOID='.', E_START='T',E_CROOM='C', E_NOTGO='X'}; 

/*int hrk (int x, int y)
{
    return abs(toX-x)+abs(toY-y);
}*/

int pos_idx(int x, int y){
    return y*(width+1) + x;    
}

deque<int> findPath(int sX, int sY, int goal)
{        
    int count=(width+1)*(height+1);  
    int x,y;  
    vector<int> dist(count, INT_MAX);
    vector<tuple<vector<int>,int>> move(count);
    deque<vector<int>> q;  
    
    q.push_back(vector<int>{sX,sY});
    dist[pos_idx(sX,sY)] = 0;
    
    cerr<<"x:"<<sX<<" y:"<<sY<<" g:"<<(char)goal<<endl;
    deque<int> path;

    while(!q.empty()){
        vector<int> c = q.front();q.pop_front();    
        for(int i=0;i<4;i++)
        {
            MOVE& m = moves[i];
             x = c[0] + m.x;
             y = c[1] + m.y;
             
             if(x < 0 || x > width || y < 0 || y > height) continue; // wrong move
             //cerr<<"["<<x<<" "<<y<<maze[y][x] ;
             if(maze[y][x] != E_WALL &&              
             dist[pos_idx(x,y)] > dist[pos_idx(c[0],c[1])]+1)
             {
                 if(goal != E_NA && maze[y][x] == E_NA)continue;
                 move[pos_idx(x,y)]=make_tuple(c, i); // move number                 
                 dist[pos_idx(x,y)] = dist[pos_idx(c[0],c[1])]+1;
                 //cerr<< m[2]<<" ("<<x<<","<<y<<"="<<maze[y][x]<<")] ";
                 if(maze[y][x] == goal) {
                     
                     int p=pos_idx(x,y); 
                     //cerr<<endl<<x<<","<<y<<"="<<maze[y][x]<<endl;
                     if(goal==E_NA) p=pos_idx(c[0],c[1]);
                     for(int v=dist[p]-1;v>=0;v--)
                     {     
                         int m=get<1>(move[p]);
                         path.push_front(m);cerr<<m<<" ";
                         vector<int> nc = get<0>(move[p]);
                         x = nc[0];
                         y = nc[1];
                         p = pos_idx(x,y);
                     }
                     
                     cerr<<"*"<<path.size()<<endl;
                     return path;
                     }
                
                 q.push_back(vector<int>{x,y});
             } //else cerr<<"] ";
        }
    }

    return path;    
}

void PrintMaze(int kr, int kc){
    int r = 0, c =0;
    for(vector<char>& v:maze) {   
        c = 0;
        for(char i:v)  {
            
            cerr<<((i==0)?'?':(c==kc && r==kr)?'K':i);
            c++;
        }
        cerr<<endl;
        r++;
    }
}


int main()
{
    int R; // number of rows.
    int C; // number of columns.
    int A; // number of rounds between the time the alarm countdown is activated and the time the alarm goes off.
    cin >> R >> C >> A; cin.ignore();
    deque<int> fp;
    width = C - 1;
    height = R - 1;
    maze.resize(R);
    for(vector<char>& v:maze) v.resize(C, E_NA);
    int finding=FIND_CROOM;
    // game loop
    while (1) {
        int KR; // row where Kirk is located.
        int KC; // column where Kirk is located.
        cin >> KR >> KC; cin.ignore();
        for (int y = 0; y < R; y++) {
            string ROW; // C of the characters in '#.TC?' (i.e. one line of the ASCII maze).
            cin >> ROW; cin.ignore();
            for (int x = 0; x < C; x++)
            {
                char c = ROW[x]; 
                if(c != '?' && maze[y][x] != E_NOTGO)  maze[y][x] = c;                
            }
        }
        PrintMaze(KR, KC);
        if(fp.empty())
        {
            if(finding == FIND_CROOM){
                fp = findPath(KC,KR,E_CROOM);
                if(fp.empty()){
                    fp = findPath(KC,KR,E_NA);                
                } else{
                    finding = FIND_TELEPORT;    
                }
            }
            else
                fp = findPath(KC,KR,E_START);                    
        }
        if(!fp.empty()){
            
            cout<<moves[fp.front()].out<<endl;
            fp.pop_front();
        }
        // Write an action using cout. DON'T FORGET THE "<< endl"
        // To debug: cerr << "Debug messages..." << endl;

       // cout << "RIGHT" << endl; // Kirk's next move (UP DOWN LEFT or RIGHT).
    }
}