Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-22

SRM232 Div1 Easy: WordFind

| 05:11 | SRM232 Div1 Easy: WordFind - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM232 Div1 Easy: WordFind - naoya_t@topcoder SRM232 Div1 Easy: WordFind - naoya_t@topcoder のブックマークコメント

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

  • 223.81points →縦・横・斜めのうち最初に見つけたやつを返してたのでfailed system test
  • 縦・横・斜めまでちゃんと調べてからソート。passed system test
  • 問題文の例が通ったからと言って油断しないこと
class WordFind {
  string str(int y, int x){
    stringstream ss;
    ss << y << " " << x;
    return ss.str();
  }
 public:
  vector <string> findWords(vector <string> grid, vector <string> wordList) {
    int gw=sz(grid[0]),gh=sz(grid);
    int n=sz(wordList);
    vs ans(n,"");
    rep(i,n){
      vector<pair<int,int> > buf;
      string w=wordList[i]; char w0=w[0]; int l=sz(w);
      // yoko
      for(int y=0;y<gh;y++){
        for(int x=0;x<=gw-l;x++){
          if(grid[y][x]!=w0) goto fail1;
          for(int z=1;z<l;z++){
            if(grid[y][x+z]!=w[z]) goto fail1;
          }
          buf.pb(make_pair(y,x));
          goto cont1; 
       fail1:;
        }
      }
   cont1:
      // tate
      for(int y=0;y<=gh-l;y++){
        for(int x=0;x<gw;x++){
          if(grid[y][x]!=w0) goto fail2;
          for(int z=1;z<l;z++){
            if(grid[y+z][x]!=w[z]) goto fail2;
          }
          buf.pb(make_pair(y,x));
          goto cont2;
       fail2:;
        }
      }
   cont2:
      // naname
      for(int y=0;y<=gh-l;y++){
        for(int x=0;x<=gw-l;x++){
          if(grid[y][x]!=w0) goto fail3;
          for(int z=1;z<l;z++){
            if(grid[y+z][x+z]!=w[z]) goto fail3;
          }
          buf.pb(make_pair(y,x));
          goto cont3;
       fail3:;
        }
      }
   cont3:
      sort(all(buf));
      if (sz(buf) > 0) ans[i] = str(buf[0].first, buf[0].second);
    }
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090522