---
# System prepended metadata

title: Generals.io Algorithm

---

# Generals.io Algorithm

## Wiki

https://wiki.generals.io/

## Opening

![](https://hackmd.io/_uploads/Bkeu9PZPrn.png)

### 考慮在一開始不會遇到敵人的情況

25army and 50steps

How many steps for one round?

* flood fill
    * calculate steps(bfs)
    * find the way(dfs)
      => choose the optimal path    
    * generally, the second path should try not to pass the same cell that has passed in the first path      

 * Greedy 很好的規則 (22) -> Optimal solution (23)

25 (12 6 3 2 1)

### some smiliar problem

#### ***Subgraph isomorphism problem***

**definition** :

two graphs G and H are given as input, and one must determine whether G contains a subgraph that is [isomorphic](https://en.m.wikipedia.org/wiki/Graph_isomorphism) to H. 
     


a generalization of both the maximum [clique problem](https://en.m.wikipedia.org/wiki/Clique_problem) and the problem of testing whether a graph contains a [Hamiltonian cycle](https://en.wikipedia.org/wiki/Hamiltonian_path), and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.


#### ***Vehicle routing problem***

## Future (R-tree)

![](https://hackmd.io/_uploads/HJ5A0Zwr3.png)
