「Path on a Grid」の編集履歴（バックアップ）一覧に戻る

Path on a Grid - (2015/08/20 (木) 03:04:39) のソース

AOJ問38 Path on a Grid 

一見ややこしく見えるが、右手を壁にというのがヒント。
左手を壁につけて歩いてることがない。
ということで４方向の移動だけ考えればいいと理解できる。
後は配列で回すだけです。
上向きにあるているときはマップを上から見て壁の左側にいるし下向きに歩いているときは壁の右側にいる。
ということに気付けば実装は簡単になります。

 #include<stdio.h>
 #include<string>
 #include<vector>
 #include<iostream>
  
 std::vector<std::string> map;
 
 
 int main(){
    std::string line;
    char c;
    while(1){
        std::cin>>line;
        if(std::cin.eof()==true)break;
        if(line!="")map.push_back(line);
    }
    int r=0;
    int px=1,py=0;
    int dx[4]={0,0,-1,0};
    int dy[4]={0,-1,0,1};
    int dx2[4]={1,0,-1,0};
    int dy2[4]={0,-2,0,2};
    char rs[5]="RULD";
    printf("R");
    while(px!=0||py!=0){
        for(int i=0;i<4;i++){
            int r2=(r+5-i)%4;
            int x=px+dx[r2];
            int y=py+dy[r2];
            //printf("(%d %d %d)",r2,x,y);
            if(x<0||y<0||y>=map.size())continue;
            if(x>=map[y].size())continue;
            if(map[y][x]=='1'){
                px+=dx2[r2];
                py+=dy2[r2];
                r=r2;
                printf("%c",rs[r2]);
                break;
            }
         }
     }
     
     printf( "\n");
 }