naoya_t@topcoder

SRM232 Div1 Easy: WordFind

過去問, 練習, Tutorials | 05:11 |

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

• 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;
  }
};