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重ループで書かれてる人を見つけた。ぜんぜん考えが及ばなかった…。