Chinaunix首页 | 论坛 | 博客
  • 博客访问: 11461
  • 博文数量: 3
  • 博客积分: 146
  • 博客等级: 民兵
  • 技术积分: 40
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-10 18:27
文章分类

全部博文(3)

文章存档

2012年(3)

最近访客

分类: 嵌入式

2012-01-10 20:00:48

  1. /*
  2.  * 都市摩天楼最佳布局计算,
  3.  * 第一版本,房屋不可拆除时版本,
  4.  * 速度比较快,
  5.  * 5x5找到56的解,不知是否已经最优?
  6.  * 1 2 1 2 3
  7.  * 2 4 3 4 1
  8.  * 4 1 2 1 3
  9.  * 3 2 1 3 2
  10.  * 1 4 3 2 1
  11.  * winxos 2012-01-07
  12.  */
  13. using System;
  14. using System.Collections.Generic;
  15. using System.Text;

  16. namespace game
  17. {
  18.     class Program
  19.     {
  20.         struct Point
  21.         {
  22.             public Point(int x,int y)
  23.             {
  24.                 X=x;
  25.                 Y=y;
  26.             }
  27.             public int X;
  28.             public int Y;
  29.         }
  30.         class boardgame
  31.         {
  32.             private int[,] map;
  33.             private int[,] map_build;
  34.             const int MAPSIZE = 5;
  35.             public int Value
  36.             {
  37.                 get { return CalcBoardSum(); }
  38.             }
  39.             public boardgame()
  40.             {
  41.                 map = new int[MAPSIZE, MAPSIZE];
  42.                 map_build = new int[MAPSIZE, MAPSIZE];
  43.             }
  44.             public void ReSet() //clear
  45.             {
  46.                 for (int i = 0; i < map.GetLength(0); i++)
  47.                 {
  48.                     for (int j = 0; j < map.GetLength(1); j++)
  49.                     {
  50.                         map[i, j] = 0;
  51.                         map_build[i, j] = 0;
  52.                     }
  53.                 }
  54.             }
  55.             public bool FinishBoard() //auto finish
  56.             {
  57.                 Random rnd = new Random();
  58.                 for (int i = 0; i < MAPSIZE * MAPSIZE; i++)
  59.                 {
  60.                     CalcBuildMap();
  61.               // ShowBuildMap();
  62.                     for (int j = 4; j > 0; j--)
  63.                     {
  64.                         List<Point> lp = GetValid(j);
  65.                         if (lp.Count > 0)
  66.                         {
  67.                             FillBoard(j, lp[rnd.Next(lp.Count)]);
  68.                             break;
  69.                         }
  70.                     }
  71.              // Console.WriteLine("@");
  72.              // ShowBoard();
  73.                 }
  74.              // Console.WriteLine(CalcBoardSum());
  75.                 return true;
  76.             }
  77.             public void ShowBoard()
  78.             {
  79.                 ShowMap(map);
  80.             }
  81.             public void ShowBuildMap()
  82.             {
  83.                 ShowMap(map_build);
  84.             }
  85.             void ShowMap(int[,] map)
  86.             {
  87.                 for (int i = 0; i < map.GetLength(0); i++)
  88.                 {
  89.                     for (int j = 0; j < map.GetLength(1); j++)
  90.                     {
  91.                         Console.Write("{0,2}",map[i, j]);
  92.                     }
  93.                     Console.WriteLine();
  94.                 }
  95.             }
  96.             void ShowList(List<int> li)
  97.             {
  98.                 foreach(int i in li)
  99.                 {
  100.                     Console.Write("{0,2}",i);
  101.                 }
  102.                 Console.WriteLine();
  103.             }
  104.             void ShowListPoint(List<Point> lp)
  105.             {
  106.                 foreach (Point p in lp)
  107.                 {
  108.                     Console.Write("{0},{1}\n", p.X,p.Y);
  109.                 }
  110.                 Console.WriteLine();
  111.             }
  112.             void FillBoard(int n, Point p)
  113.             {
  114.                 map[p.X, p.Y] = n;
  115.             }
  116.             int CalcBoardSum() //
  117.             {
  118.                 int sum = 0;
  119.                 for (int i = 0; i < map.GetLength(0); i++)
  120.                 {
  121.                     for (int j = 0; j < map.GetLength(1); j++)
  122.                     {
  123.                         sum += map[i, j];
  124.                     }
  125.                 }
  126.                 return sum;
  127.             }
  128.             List<int> GetNabor(int x, int y) //
  129.             {
  130.                 List<int> li = new List<int>();
  131.                 if (x < 0 || x >= map.GetLength(0) || y < 0 || y >= map.GetLength(1))
  132.                 {
  133.                     return li;
  134.                 }
  135.                 if (x == 0 && y == 0) //left top
  136.                 {
  137.                     li.Add(map[x, y+1]);
  138.                     li.Add(map[x+1, y]);
  139.                 }
  140.                 else if (x == map.GetLength(0) - 1 && y == map.GetLength(1) - 1) //right bottom
  141.                 {
  142.                     li.Add(map[x-1, y]);
  143.                     li.Add(map[x, y-1]);
  144.                 }
  145.                 else if (x == map.GetLength(0) - 1 && y == 0) //right top
  146.                 {
  147.                     li.Add(map[x - 1, y]);
  148.                     li.Add(map[x, y + 1]);
  149.                 }
  150.                 else if (x == 0 && y == map.GetLength(1) - 1) //left bottom
  151.                 {
  152.                     li.Add(map[x, y-1]);
  153.                     li.Add(map[x+1, y]);
  154.                 }
  155.                 else if (x == 0) //left
  156.                 {
  157.                     li.Add(map[x, y - 1]);
  158.                     li.Add(map[x, y + 1]);
  159.                     li.Add(map[x + 1, y]);
  160.                 }
  161.                 else if (x == map.GetLength(0) - 1) //right
  162.                 {
  163.                     li.Add(map[x, y - 1]);
  164.                     li.Add(map[x, y + 1]);
  165.                     li.Add(map[x - 1, y]);
  166.                 }
  167.                 else if (y == 0) //top
  168.                 {
  169.                     li.Add(map[x - 1, y]);
  170.                     li.Add(map[x + 1, y]);
  171.                     li.Add(map[x, y + 1]);
  172.                 }
  173.                 else if (y == map.GetLength(1) - 1) //bottom
  174.                 {
  175.                     li.Add(map[x - 1, y]);
  176.                     li.Add(map[x + 1, y]);
  177.                     li.Add(map[x, y - 1]);
  178.                 }
  179.                 else //center
  180.                 {
  181.                     li.Add(map[x - 1, y]);
  182.                     li.Add(map[x + 1, y]);
  183.                     li.Add(map[x, y + 1]);
  184.                     li.Add(map[x, y - 1]);
  185.                 }
  186.                 return li;
  187.             }
  188.             void CalcBuildMap() //calc max value table can build
  189.             {
  190.                 for (int i = 0; i < map.GetLength(0); i++)
  191.                 {
  192.                     for (int j = 0; j < map.GetLength(1); j++)
  193.                     {
  194.                         if (map[i, j] != 0)
  195.                         {
  196.                             map_build[i, j] = -1;
  197.                         }
  198.                         else
  199.                         {
  200.                             List<int> li = GetNabor(i, j);
  201.                             int[] tmp=new int[5];
  202.                             foreach (int ii in li)
  203.                             {
  204.                                 tmp[ii]++;
  205.                             }
  206.                             int ix = 1;
  207.                             for (; ix < 5; ix++)
  208.                             {
  209.                                 if (tmp[ix] == 0)
  210.                                 {
  211.                                     break;
  212.                                 }
  213.                             }
  214.                             map_build[i, j] = ix;
  215.                         }
  216.                     }
  217.                 }
  218.             }
  219.             List<Point> GetValid(int n) //can not demolish
  220.             {
  221.                 List<Point> lp=new List<Point>();
  222.                 for (int i = 0; i < map_build.GetLength(0); i++)
  223.                 {
  224.                     for (int j = 0; j < map_build.GetLength(1); j++)
  225.                     {
  226.                         if (map_build[i, j] == n)
  227.                         {
  228.                             lp.Add(new Point(i, j));
  229.                         }
  230.                     }
  231.                 }
  232.                 return lp;
  233.             }

  234.         }
  235.         static void Main(string[] args)
  236.         {
  237.             int max = 0;
  238.             boardgame bg = new boardgame();
  239.             for (int i = 0; i < 50000; i++)
  240.             {
  241.                 bg.ReSet();
  242.                 bg.FinishBoard();
  243.                 if (bg.Value > max)
  244.                 {
  245.                     max = bg.Value;
  246.                     Console.WriteLine(max);
  247.                     bg.ShowBoard();
  248.                 }
  249.             }
  250.         }
  251.     }
  252. }
阅读(790) | 评论(0) | 转发(0) |
0

上一篇:code highlight test python

下一篇:没有了

给主人留下些什么吧!~~