AOJ 0037 : Path on a Grid
問題リンク:格子状の経路 | Aizu Online Judge
解法:
問題で言われている通りに書く
自分は最初にcharの2次元配列に壁や床を書き、スタート地点から人を動かしていった
dx = {+1,+0,-1,+0};
dy = {+0,+1,+0,-1};
という配列を用意して、最初の時点では0の方向を見ているものとした
ここから、もし手が壁から離れたならば今見ている方向に+1した方向へ変更し、
進んだ先が壁だったなら今見ている方向に-1した方向へ変更した
コード:
#include<iostream> #include<cassert> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define inf (1<<29) #define MAX 100 using namespace std; struct You {//手の位置は自分の座標にdx[(dir+1)%4],dy[(dir+1)%4]を加えた場所 int x,y,dir; You(int x=-inf,int y=-inf):x(x),y(y),dir(0){} }; char G[MAX][MAX]; int dx[] = {+1,+0,-1,+0}; int dy[] = {+0,+1,+0,-1}; void init() { rep(i,MAX)rep(j,MAX)G[i][j] = '.'; } void makeGraph() { string line; int x; REP(y,1,10) {//odd -> yoko, even -> tate cin >> line; x = (y%2?1:0); rep(i,line.size()) { if(line[i] == '1') { G[y][x] = (y%2?'-':'|'); if(y%2) G[y][x-1] = G[y][x+1] = 'o'; else G[y+1][x] = G[y-1][x] = 'o'; } x += 2; } } } void print() { rep(i,11) { rep(j,11) { cout << G[i][j]; } cout << endl; } cout << endl; } void compute() { You you(0,0); bool fir = true; while(true) { int x = you.x,y = you.y,dir = you.dir; int hx = x + dx[(dir+1)%4],hy = y + dy[(dir+1)%4]; if(!fir && hx == 0 && hy == 1) { cout << '\n'; return; } fir = false; int nx = x + dx[dir],ny = y + dy[dir]; hx += dx[dir],hy += dy[dir]; assert(G[ny][nx] != 'o'); if(G[ny][nx] == '|' || G[ny][nx] == '-') { dir = (dir + 3)%4; you.dir = dir; } else if(G[hy][hx] == '.') { dir = (dir + 1)%4; you.x = nx + dx[dir], you.y = ny + dy[dir],you.dir = dir; } else if(G[hy][hx] == 'o' || G[hy][hx] == '-' || G[hy][hx] == '|') { you.x += dx[dir],you.y += dy[dir]; } hx = you.x + dx[(dir+1)%4], hy = you.y + dy[(dir+1)%4]; if(G[hy][hx] != 'o') cout << (dir==0?'R':(dir==1?'D':(dir==2?'L':'U'))); } } int main() { init(); makeGraph(); compute(); return 0; }