SRM 368 DIV1 Easy - JumpingBoard (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8245&rd=10936
あるボードが存在し、その中には１～９までの数字かＨで表わされる穴が存在する。
まずは一番左上のセルからスタートし、そのセルに書いてある数だけ上下左右に移動する。ボードの外に出たらそこで終了する。
このとき、ボードの外に出るまでの最大のターン数を求める。
ただし、ループが可能でボードの外に出なくてもよい場合はー１を返す。
解き方
ＢＦＳに最初見えたがＤＦＳにて全てのルートを探索する必要がある。
ただし、一度通ったルートはメモ化が可能なのでｄｐが適用できる。
注意する点はループが発生した場合はー１を返さなければならないので、
現在探索中のルートはフラグを立てて判定しなければならない。
今回は以下のように値を割り振ることでコーディング可能。
セルを超えた時 ：０で終了
すでに探索したルート：０以上で終了（うち、ホールにあたったときは０で終了）
現在探索中のルート ：ー２で例外値を返し終了
それ以外 ：－１で次のループに進む
他の方のコードをみましたが、throw&catchしてもよさそうでした。
http://community.topcoder.com/stat?c=problem_solution&rd=10936&pm=8245&cr=251074
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[60][60];
int w,h;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
vector<string> B;
class JumpingBoard {
public:
int f(int r,int c){
if(r<0||r>=h||c<0||c>=w)return 0;
if(dp[r][c]>=0)return dp[r][c];
if(dp[r][c]==-2)return 900000;
int ret=0;
int move=B[r][c]-'0';
dp[r][c]=-2;
FORE(i,0,4)ret=max(ret,1+f(r+dx[i]*move,c+dy[i]*move));
return dp[r][c]=ret;
}
int maxJumps(vector<string> board) {
w=board[0].size(),h=board.size();
FORE(i,0,h)FORE(j,0,w){
if(board[i][j]=='H')dp[i][j]=0;
else dp[i][j]=-1;
}
B=board;
int ret=f(0,0);
return ret>900000 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[60][60];
int w,h;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
vector<string> B;
class JumpingBoard {
public:
int f(int r,int c){
if(r<0||r>=h||c<0||c>=w)return 0;
if(dp[r][c]>=0)return dp[r][c];
if(dp[r][c]==-2)return 900000;
int ret=0;
int move=B[r][c]-'0';
dp[r][c]=-2;
FORE(i,0,4)ret=max(ret,1+f(r+dx[i]*move,c+dy[i]*move));
return dp[r][c]=ret;
}
int maxJumps(vector<string> board) {
w=board[0].size(),h=board.size();
FORE(i,0,h)FORE(j,0,w){
if(board[i][j]=='H')dp[i][j]=0;
else dp[i][j]=-1;
}
B=board;
int ret=f(0,0);
return ret>900000 ? -1 : ret;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int visited[60][60],next[60][60];
class JumpingBoard {
public:
int maxJumps(vector<string> board) {
int h=board.size(),w=board[0].size();
int dr[]={0,0,1,-1};
int dc[]={1,-1,0,0};
int INF=h*w+10,ret=0;
memset(next,0,sizeof(next));
memset(visited,0,sizeof(visited));
visited[0][0]=1;
while(ret<INF){
int valid=0;
memset(next,0,sizeof(next));
ret++;
FORE(i,0,h)FORE(j,0,w)if(visited[i][j]){
int cnt=board[i][j]-'0';
FORE(k,0,4){
int nr=i+cnt*dr[k];
int nc=j+cnt*dc[k];
if(0<=nr && nr<h && 0<=nc && nc<w && board[nr][nc]!='H'){
next[nr][nc]=1;
valid=1;
}
}
}
FORE(i,0,h)FORE(j,0,w)visited[i][j]=next[i][j];
if(!valid)break;
}
return ret==INF ? -1 :ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int visited[60][60],next[60][60];
class JumpingBoard {
public:
int maxJumps(vector<string> board) {
int h=board.size(),w=board[0].size();
int dr[]={0,0,1,-1};
int dc[]={1,-1,0,0};
int INF=h*w+10,ret=0;
memset(next,0,sizeof(next));
memset(visited,0,sizeof(visited));
visited[0][0]=1;
while(ret<INF){
int valid=0;
memset(next,0,sizeof(next));
ret++;
FORE(i,0,h)FORE(j,0,w)if(visited[i][j]){
int cnt=board[i][j]-'0';
FORE(k,0,4){
int nr=i+cnt*dr[k];
int nc=j+cnt*dc[k];
if(0<=nr && nr<h && 0<=nc && nc<w && board[nr][nc]!='H'){
next[nr][nc]=1;
valid=1;
}
}
}
FORE(i,0,h)FORE(j,0,w)visited[i][j]=next[i][j];
if(!valid)break;
}
return ret==INF ? -1 :ret;
}
};
