naoya_t@topcoder

SRM197 Div1 Easy: GeneralChess

過去問, 練習, Tutorials | 02:59 |

Algorithm Tutorials: How To Find a Solution (by Dumitru) より。Brute Forceで解く例。

• まあやるだけですが
• knightの動ける位置とかコピペで行けるようにしておくべきだ
• 197.98points (15'25'') 時間かけすぎ
• Passed System Test

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<int,int> ii;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

// split(), map_atoi() は自作

int knight[8][2] = { {-2,-1}, {-2,1}, {-1,-2}, {-1,2}, {1,-2}, {1,2}, {2,-1}, {2,1} };

class GeneralChess {
 public:
  vector <string> attackPositions(vector <string> pieces) {
    int n=sz(pieces);
    map<ii,int> m;
    rep(i,n){
      vi xy = map_atoi(split(pieces[i],','));
      rep(j,8){
        ii xy_ = make_pair(xy[0] + knight[j][0],
                           xy[1] + knight[j][1]);
        if (found(m,xy_)) m[xy_]++;
        else m[xy_]=1;
      }
    }
    vector<ii> v;
    tr(m,it){
      if(it->second==n) v.pb(it->first);
    }
    sort(all(v));
    vector<string> ans;
    tr(v,it){
      char buf[14];
      sprintf(buf,"%d,%d", it->first, it->second);
      ans.pb(buf);
    }
    return ans;
  }
};