ichirin2501's diary

いっちりーん。

SRM253 DIV2 1000pts

また診断人さんのニコ生に突撃してきた。

SRM253 DIV2 1000pts

50*50以下のマップ情報が与えられて、Aからアルファベット順に何歩進めるか(8方向)という問題です。



普通に再帰を利用して解いてみた。

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
const int dx[]={0,1,1,1,0,-1,-1,-1};
const int dy[]={-1,-1,0,1,1,1,0,-1};
int ans,H,W,map[50][50],flag;

class ABCPath{
public:
  void search(int x,int y,int cnt,char moji,vector<string>& grid){

    if(ans<cnt && flag)ans=cnt;
    if(map[y][x]<cnt)map[y][x]=cnt;
    else return;
    
    for(int k=0;k<8;k++){
      int tx=x+dx[k];
      int ty=y+dy[k];
      if(tx<0 || tx>=W || ty<0 || ty>=H || grid[ty][tx]!=moji+1)continue;
      search(tx,ty,cnt+1,moji+1,grid);
    }
  }
  int length(vector<string> grid){
    memset(map,0,sizeof(map));
    H=grid.size();
    W=grid[0].size();
    
    for(int i=0;i<grid.size();i++){
      for(int j=0;j<grid[i].size();j++){
        if(map[i][j]==0){
          flag=grid[i][j]=='A'?1:0;
          search(j,i,1,grid[i][j],grid);
        }
      }
    }
    return ans;
  }
};

早々に解けて提出して正解したのだけど、後で見ればバグ有りだったので再提出したら点数下がった。
正解した後に提出しても点数下がるんだなぁ。
どの文字からも検索かけてメモ化してるのだけど、文字Aを見つけたときだけ検索をかけたほうが速い?

Code Jamの他の方のソースコードを見て反省しました。
俺のコード…アルゴリズムからして無駄がありすぎるwwww泣いたwww。
問題A,Cは30行、問題Bは50行前後で書けますね。
解法が見えてすぐ書き始める前に少し立ち止まって、
より簡潔に書ける解法(視点切り替え)を模索したほうが結果的に早く書き終わるのかも。
早く・短く・ユニークにコードを書いていきたいです。



追記:
8方向の探索は予め配列に値を用意させたけれど、8方向の場合は

for(dy=-1;dy<=1;dy++)
    for(dx=-1;dx<=1;dx++)

2重ループで書かれてる人を見つけた。ぜんぜん考えが及ばなかった…。