POJ 1629 - Fillword

http://poj.org/problem?id=1629

概要

M x N のグリッドが与えられ，各マスには大文字のアルファベットが書かれている． そのグリッドの中には与えられた P 個の単語が並べられている．

どの単語にも使われないようなアルファベットを小さいほうがらすべて答える．

単語 W が「並んでいる」とは，各アルファベットのマスが順に (x[1],y[1]), ..., (x[k], y[k]) のとき， |x[i]-x[i+1]| + |y[i]-y[i+1]| = 1 for each i = 1, ..., k-1 であることを言う．

また，あるマスが2つ以上の単語に使われることは無く，あるマスが1つの単語中で2回以上使われることも無い．

制約

解法

M, N が小さめだし探索するのかなーと思ったが，解が必ず存在して，1つのマスは1回しか使われないので，単に各アルファベットの数を数えればいいだけだった．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, M, P;
 8   cin >> N >> M >> P;
 9   vector<int> cnt(26, 0);
10   for (int i = 0; i < N; i++) {
11     string s;
12     cin >> s;
13     for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
14       ++cnt[*it-'A'];
15     }
16   }
17   for (int i = 0; i < P; i++) {
18     string s;
19     cin >> s;
20     for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
21       --cnt[*it-'A'];
22     }
23   }
24   for (int i = 0; i < 26; i++) {
25     for (int j = 0; j < cnt[i]; j++) {
26       cout << char('A'+i);
27     }
28   }
29   cout << endl;
30   return 0;
31 }
poj/1629.cc