Hatena::Grouptopcoder

cou929のTopCoder日記

2009-11-04

SRM211 div1 (過去問)

00:48

Easy - grafixCorrupt

辞書(stringvector)とある単語(string)が与えられる。辞書の中から単語と一番一致度が高い単語を取り出す。

普通に一つ一つ調べていくだけです。

class grafixCorrupt {
public:
  int selectWord(vector <string> dictionary, string candidate)
  {
    int maximum = 0;
    int index = -1;

    for (int i=0; i<dictionary.size(); i++)
      {
	int c = 0;
	for (int j=0; j<dictionary[i].size(); j++)
	  if (dictionary[i][j] == candidate[j])
	    c++;

	if (c > maximum)
	  {
	    maximum = c;
	    index = i;
	  }
      }

    return index;
  }
};

Medium - grafixMask

400x600 pixelの画像がある。またマスクがあり、マスクは矩形の集合で定義されている。マスクがない領域を調べ、領域の広い順にソートし返す。

アプローチとしては、まず画像を表す配列を準備し、マスクになるピクセルを埋めていきます。次にマスクされていない領域をラベリングしていき、最後に領域の大きさを調べてソートします。

class grafixMask {
public:
  int image[400][600];
  int labelCounter;

  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

  vector <int> split(const string _s, const string del)
  {
    vector <int> ret;
    string s = _s;

    while (!s.empty())
      {
	size_t pos = s.find(del);
	string sub = "";
	sub = s.substr(0, pos);
	ret.push_back(toInt(sub));
	if (pos != string::npos)
	  pos += del.size();
	s.erase(0, pos);
      }

    return ret;
  }

  bool inRange(int row, int col)
  {
    if (0 <= row && row < 400 && 0 <= col && col < 600)
      return true;
    return false;
  }

  int drawRectangle(int x1, int y1, int x2, int y2)
  {
    for (int row=x1; row<=x2; row++)
      for (int col=y1; col<=y2; col++)
	image[row][col] = 0;

    return 0;
  }

  int label(int row, int col)
  {
    queue <pair <int, int> > q;
    q.push(make_pair(row, col));

    int xdir[4] = {0, 1, 0, -1};
    int ydir[4] = {-1, 0, 1, 0};

    while (!q.empty())
      {
	pair <int, int> current = q.front();
	q.pop();

	for (int i=0; i<4; i++)
	  if (inRange(current.first+xdir[i], current.second+ydir[i]) && image[current.first+xdir[i]][current.second+ydir[i]] == -1)
	    {
	      image[current.first+xdir[i]][current.second+ydir[i]] = labelCounter;
	      q.push(make_pair(current.first+xdir[i], current.second+ydir[i]));
	    }
      }
    
    labelCounter++;

    return 0;
  }

  vector <int> sortedAreas(vector <string> rectangles)
  {
    memset(image, -1, sizeof(image));
    labelCounter = 1;

    for (int i=0; i<(int)rectangles.size(); i++)
      {
	vector <int> coords = split(rectangles[i], " ");
	drawRectangle(coords[0], coords[1], coords[2], coords[3]);
      }

    for (int row=0; row<400; row++)
      for (int col=0; col<600; col++)
	if (image[row][col] == -1)
	  {
	    image[row][col] = labelCounter;
	    label(row, col);
	  }

    vector <int> ret(labelCounter-1, 0);

    for (int row=0; row<400; row++)
      for (int col=0; col<600; col++)
	if (image[row][col] != 0)
	  ret[image[row][col]-1]++;

    sort(ret.begin(), ret.end());

    return ret;
  }
};