图形算法的C读网格到数组 [英] Graph algorithm in C by reading grids into array

问题描述

我需要阅读一些物体console.It有点像战舰比赛C写的。 想到这我的6x6 array.I的平台正在采取从用户的用户输入和字符X表示这是在二维array.I阴影区正在分配的字符为36 place.The例子用户阵列后给出的输入是;

I need to read some objects from console.It is a bit like the battleship game written in C. Think of it I have a platform of 6x6 array.I am taking the user input from the user and the char 'X' means it is a shaded area in the two dimensional array.I am assigning the chars for the 36 place.The example of the array after user has given the inputs is;

0,0                       0,6      

  X              XXX
 X                X  
   XX             X 
     X




6,0                       6,6

抱歉输出不是太clear.It是X的输出碳化该用户不得不entered.The的x在两组字符被合并，因此，也有在graph.I 2对象需要计数在X字符的groups.The方向的数量不能够成为对称的，所有的事情是可能存在组X字符该被合并，我要计数的基团

Sorry the output is not too clear.It is the output of the X chars that user had entered.The 'x' chars in the two groups are unioned and so, there are 2 objects in the graph.I need to count the number of the groups.The direction of the X chars is not able to be symetric, all the thing is there may be group of x chars that are unioned and i want to count the groups

推荐答案

模式的问题，因为图（因为你已经了解）： G =（V，E） ，其中 V 是你的网格（或仅 X 的更准确），而 E = {（U，V）|还有为X在这两个u和v}

Model the problem as the graph (as you already understood): G=(V,E), where V is your grid (or only the x's to be more exact), and E = { (u,v) | there is X in both u and v }

在解析，保存所有的坐标，在一个容器中，并且每个映射到一个布尔值，表示如果有人访问过与否。

During parsing, save all your coordinates in an container, and map each to a boolean value indicating if it was visited or not.

现在，重复，同时还有非参观X的：
运行图发现算法（ BFS 就是一个例子），从这个（没有访问） X ，并标记所有访问过的 X 的发现算法的运行过程中遇到的

Now, repeat while there are still non visited x's:
Run a graph discovery algorithm (BFS is an example) from this (not visited) x, and mark all visited x's encountered during the run of the discovery algorithm

迭代次数（次BFS被调用数目）是组的数目

The number of iterations (number of times BFS was invoked) is the number of groups.

这篇关于图形算法的C读网格到数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！