2011年華はプログラミング大会のテーマです

3.バス停の場所探し(50分)
l  
問題の説明
1つのN*N 2次元マトリクスは都市レイアウトを表し、要素値は'.','のみである.X',‘B',‘S',Xは現在の位置を表し,Bはバリケードを表し,Sはバス停を表す.’実行可能なパスを表します.現在、所与の経路長Yは、到達可能なバス停の個数を見つけ、経路にバリアを含めることはできない.
パスの長さの定義:
1、 
ノードとそれ自体の距離は0です.
2、 
ノードとその上、下、左、右の4つの隣接ノードの距離はすべて1です.
l  
要求実装関数
int FindStat(const char*Map,unsigned int iArrN,unsigned int iPathLen)【入力】Map:都市レイアウトiArrN:都市レイアウトマトリクスの行数iPathLen:所与の経路長【出力】なし【戻る】到着可能なバス停数注:入力行列は、一次元で保存された二次元配列であり、例えば、「A」、「B」、「C」、「D」、「E」、「F」、「G」、「H」、「I」と入力され、実際には以下の3*3の行列「A」、「B」、「C」、「D」、「E」、「F」、「G」、「H」、「I」を表す
l  
例
入力:「...S.....X.S.....S....」5,3リターン:2入力:“S…S……BS……..X”,5,5リターン:1

#include<stdio.h>
#include<stdlib.h>
#include<queue>

int FindStat (const char *Map, unsigned int iArrN, unsigned int iPathLen)
{
  int arrCount = iArrN*iArrN;
  int iVisited, xDirect, sum = 0;
  int locationX = -1;
  char* visited = (char *)malloc(arrCount * sizeof(char));
  int* path = (int *)malloc(arrCount * sizeof(int));

  for(int i = 0; i < arrCount; i++)
    {
      if(Map[i] == '.'||Map[i] == 'S') visited[i] = -1;
      else if(Map[i] == 'B')
    {
      visited[i] = 0;
      path[i] = -1;
    }
      if(Map[i] == 'X') locationX = i;
     
    }


  std::queue<int> myqueue;
  visited[locationX] = 1;
  myqueue.push(locationX);
  while(!myqueue.empty())
    {
      iVisited = myqueue.front();
      myqueue.pop();
      xDirect = iVisited + 5;
      if((xDirect) < arrCount) 
    if(visited[xDirect] == -1)
      {
        path[xDirect] = path[iVisited] + 1;
        visited[xDirect] = 1;
        myqueue.push(xDirect);
      }
      xDirect = iVisited - 5;
      if((xDirect) >= 0) 
    if(visited[xDirect] == -1)
      {
        path[xDirect] = path[iVisited] + 1;
        visited[xDirect] = 1;
        myqueue.push(xDirect);
      }
      xDirect = iVisited +1;
        if(iVisited%5 != 4) 
    if(visited[xDirect] == -1)
      {
        path[xDirect] = path[iVisited] + 1;
        visited[xDirect] = 1;
        myqueue.push(xDirect);
      }
      xDirect = iVisited - 1;
      if((xDirect) >= 0) 
    if(visited[xDirect] == -1)
      {
        path[xDirect] = path[iVisited] + 1;
        visited[xDirect] = 1;
        myqueue.push(xDirect);
      }

    }
for(int i = 0; i < arrCount; i++)
    {
      if(Map[i] == 'S'&&path[i]<=iPathLen) sum++;
      if(i%5 == 0)printf("
");
    printf("%d", path[i]);
    }
printf("
%d
",sum);
free(visited);
free(path);
}

int main()
{
  // char map1[] = "S...S.........BS........X";
  char map[]="...S........X.S.....S....";
   FindStat(map, 5, 3);
  // FindStat(map1, 5, 5);
}