[JAVA] J'ai essayé d'implémenter l'algorithme FloodFill avec TRON BATTLE de CodinGame

\ # Cet article est une continuation de "CodinGame peut être le bon moyen de profiter du combat avec BOT (programme AI)".

J'ai modifié le programme TRON BATTLE de CodinGame afin qu'il puisse générer la sortie de débogage suivante.

P=0
Input{X0:2, Y0:2, X1:10, Y1:0}
+ + + + + + + + + + 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

1. La source résultante

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Player
{
    static void Main(string[] args) {
        Player control = new Player();
        string[] numbers;
        Input[] inputs;
        // game loop
        while (true) {
            numbers = Console.ReadLine().Split(' ');
            int N = int.Parse(numbers[0]);
            int P = int.Parse(numbers[1]);
            Console.Error.WriteLine("P={0}", P);
            inputs = new Input[N];
            for (int i = 0; i < N; i++) {
                numbers = Console.ReadLine().Split(' ');
                int X0 = int.Parse(numbers[0]);
                int Y0 = int.Parse(numbers[1]);
                int X1 = int.Parse(numbers[2]);
                int Y1 = int.Parse(numbers[3]);
                inputs[i] = new Input(i, X0, Y0, X1, Y1);
            }
            Input me = inputs[P];
            string dir = control.HandleInputs(me, inputs);
            control.DumpMap();
            Console.WriteLine(dir);
        }
    }
    Cell[,] map = new Cell[30, 20];
    Queue<Cell> ffQueue = new Queue<Cell>();
    private Player() {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                map[x, y] = new Cell(x, y, -1);
            }
        }
    }
    private string HandleInputs(Input me, Input[] inputs) {
        Console.Error.WriteLine(me);
        foreach(var input in inputs) {
            if (input.X1 < 0) DeleteIdsFromMap(input.Id);
            else AddInputToMap(input);
        }
        ExecuteFloodfill(me);
        if (CanMoveTo(me, -1, 0)) return "LEFT";
        if (CanMoveTo(me, 1, 0)) return "RIGHT";
        if (CanMoveTo(me, 0, -1)) return "UP";
        if (CanMoveTo(me, 0, 1)) return "DOWN";
        return "?";
    }
    void AddInputToMap(Input input) {
        this.map[input.X1, input.Y1].V = input.Id;
    }
    void DeleteIdsFromMap(int id) {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == id) map[x, y].V = -1;
            }
        }
    }
    bool CanMoveTo(Input me, int xOffset, int yOffset) {
        int x = me.X1+xOffset;
        int y = me.Y1+yOffset;
        if (x < 0) return false;
        if (x > 29) return false;
        if (y < 0) return false;
        if (y > 19) return false;
        return map[x, y].V == -1 || map[x, y].V == 9;
    }
    bool IsEmptyCell(Cell center, int xOffset, int yOffset) {
        int x = center.X+xOffset;
        int y = center.Y+yOffset;
        if (x < 0) return false;
        if (x > 29) return false;
        if (y < 0) return false;
        if (y > 19) return false;
        return map[x, y].V == -1;
    }
    void DumpMap() {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == -1) Console.Error.Write("-");
                else if (map[x, y].V == 9) Console.Error.Write("+");
                else Console.Error.Write(map[x, y].V);
                Console.Error.Write(" ");
            }
            Console.Error.WriteLine();
        }
    }
    void ExecuteFloodfill(Input me) {
        for(int y=0; y<20; y++) {
            for(int x=0; x<30; x++) {
                if (map[x, y].V == 9) map[x, y].V = -1;
            }
        }
        Cell c = map[me.X1, me.Y1];
        if (IsEmptyCell(c, -1, 0)) ffQueue.Enqueue(map[c.X-1, c.Y]);
        if (IsEmptyCell(c, 1, 0)) ffQueue.Enqueue(map[c.X+1, c.Y]);
        if (IsEmptyCell(c, 0, -1)) ffQueue.Enqueue(map[c.X, c.Y-1]);
        if (IsEmptyCell(c, 0, 1)) ffQueue.Enqueue(map[c.X, c.Y+1]);
        FloodfillLoop();
    }
    void FloodfillLoop() {
        while(ffQueue.Count > 0) {
            Cell c = ffQueue.Dequeue();
            if(map[c.X, c.Y].V != -1) continue;
            c.V = 9;
            if (IsEmptyCell(c, -1, 0)) ffQueue.Enqueue(map[c.X-1, c.Y]);
            if (IsEmptyCell(c, 1, 0)) ffQueue.Enqueue(map[c.X+1, c.Y]);
            if (IsEmptyCell(c, 0, -1)) ffQueue.Enqueue(map[c.X, c.Y-1]);
            if (IsEmptyCell(c, 0, 1)) ffQueue.Enqueue(map[c.X, c.Y+1]);
        }
    }
}
class Input
{
    public int Id;
    public int X0;
    public int Y0;
    public int X1;
    public int Y1;
    public Input(int id, int x0, int y0, int x1, int y1) {
        this.Id = id;
        this.X0 = x0;
        this.Y0 = y0;
        this.X1 = x1;
        this.Y1 = y1;
    }
    public override string ToString() {
        return String.Format("Input{{X0:{0}, Y0:{1}, X1:{2}, Y1:{3}}}", X0, Y0, X1, Y1);
    }
}
class Cell
{
    public int X;
    public int Y;
    public int V;
    public Cell(int x, int y, int v) {
        this.X = x;
        this.Y = y;
        this.V = v;
    }
    public override string ToString() {
        return String.Format("Cell{{X:{0}, Y:{1}, V:{2}}}", X, Y, V);
    }
}

2. Enfin

C'est peut-être la fin de l'article que j'écris sur TRON BATTLE. Je l'ai posté avec l'espoir qu'il servira de référence pour ceux qui sont confrontés à un défi avec C #.

\ # Je veux sortir de la Ligue Wood 1 ...

Recommended Posts

J'ai essayé d'implémenter l'algorithme FloodFill avec TRON BATTLE de CodinGame
Visualisez le comportement de l'algorithme de tri avec matplotlib
J'ai lu et implémenté les variantes de UKR
J'ai mesuré les performances d'un million de documents avec mongoDB
Implémentation de l'algorithme "Algorithm Picture Book" en Python3 (Heap Sort Edition)
J'ai étudié l'algorithme d'apprentissage de renforcement du trading d'algorithmes
J'ai essayé de trouver l'entropie de l'image avec python
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
J'ai écrit la grammaire de base de Python dans Jupyter Lab
Implémentation de l'algorithme de "Algorithm Picture Book" en Python3 (Bubble Sort)
J'ai écrit le fonctionnement de base de matplotlib dans Jupyter Lab
Implémentation de l'algorithme «Algorithm Picture Book» en Python3 (tri sélectif)
J'ai comparé la vitesse de Hash avec Topaz, Ruby et Python
J'ai essayé de gratter le classement du calendrier de l'avent Qiita avec Python
Trouvez la valeur optimale de la fonction à l'aide d'un algorithme génétique (partie 2)
J'ai essayé d'automatiser l'arrosage du pot avec Raspberry Pi
[Introduction à StyleGAN] J'ai joué avec "The Life of a Man" ♬
Je veux sortir le début du mois prochain avec Python
Résolution du labyrinthe avec Python-Supplément au chapitre 6 de la référence rapide de l'algorithme-
J'ai étudié avec Kaggle Start Book basé sur kaggle [Partie 1]
J'ai écrit le fonctionnement de base de Pandas dans Jupyter Lab (partie 1)
J'ai essayé d'agrandir la taille du volume logique avec LVM
Je veux vérifier la position de mon visage avec OpenCV!
J'ai essayé d'exécuter la partie DNN d'OpenPose avec le processeur Chainer
J'ai vérifié l'image de l'Université des sciences sur Twitter avec Word2Vec.
J'ai essayé d'améliorer l'efficacité du travail quotidien avec Python
J'ai écrit le fonctionnement de base de Pandas dans Jupyter Lab (partie 2)
J'ai essayé d'implémenter Attention Seq2Seq avec PyTorch
J'ai aimé le tweet avec python. ..
Implémentation de la méthode Dyxtra par python
J'ai essayé de créer Othello AI avec tensorflow sans comprendre la théorie de l'apprentissage automatique ~ Battle Edition ~
J'ai remplacé le calcul numérique de Python par Rust et comparé la vitesse
Calculer l'itinéraire le plus court d'un graphe avec la méthode Dyxtra et Python
J'ai essayé d'obtenir le code d'authentification de l'API Qiita avec Python.
J'ai vectorisé l'accord de la chanson avec word2vec et je l'ai visualisé avec t-SNE
Je veux exprimer mes sentiments avec les paroles de Mr. Children
J'ai essayé d'extraire automatiquement les mouvements des joueurs Wiire avec un logiciel
J'ai essayé d'analyser la négativité de Nono Morikubo. [Comparer avec Posipa]
J'ai fait GAN avec Keras, donc j'ai fait une vidéo du processus d'apprentissage.
J'ai essayé de rationaliser le rôle standard des nouveaux employés avec Python
J'ai essayé de visualiser le texte du roman "Weather Child" avec Word Cloud
Je souhaite arrêter la suppression automatique de la zone tmp dans RHEL7
J'ai essayé d'obtenir les informations sur le film de l'API TMDb avec Python
J'ai fait une erreur en récupérant la hiérarchie avec MultiIndex of pandas
J'ai mesuré la vitesse de la notation d'inclusion de liste, pendant et pendant avec python2.7.
J'ai essayé de prédire le comportement du nouveau virus corona avec le modèle SEIR.
J'ai vérifié le contenu du volume du docker
J'ai essayé le serveur asynchrone de Django 3.0
J'ai essayé d'implémenter la régularisation Shake-Shake (ShakeNet) avec PyTorch
Alignez la taille de la barre de couleurs avec matplotlib
J'ai vérifié les options de copyMakeBorder d'OpenCV
Gymnastique algorithmique 24 Milieu de la liste liée
La structure des dossiers de Flask est résumée
Vérifier l'existence du fichier avec python
[Scikit-learn] J'ai joué avec la courbe ROC
Rechercher le labyrinthe avec l'algorithme python A *
Je ne connaissais pas les bases de Python
La troisième nuit de la boucle avec pour