UVa 736 Lost in Space

Lost in Space
http://uva.onlinejudge.org/external/7/736.html

問題概要

空白を含む文字が入ったグリッドが与えられる。
文字列のクエリが与えられる。
ある場所からどの方向に読めばその文字列が得られるか、
行、列、方向（北から時計回り）優先順に、すべて列挙せよ。
ただし、空白からはじまることはなく、
クエリに空白はこず、
グリッド中の空白は読み飛ばす。

解法

全探索。

ソース

#include<iostream>
#include<string>

#define REP(i, b, n) for(int i = b; i<n; i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

const int N = 50;
const string D[] = {"N", "NE", "E", "SE", "S", "SW", "W", "NW"};
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};

int n;
string s[N];
bool invalid(int y, int x){
 if(y < 0 || x < 0)return true;
 if(y >= n || x >= n)return true;
 return false;
}

bool ok(string target, int y, int x, int d){
 int cnt = 0;
 while(1){
   if(s[y][x] != ' '){
     if(target[cnt] != s[y][x])return false;
     cnt++;
     if(cnt == (int)target.length())return true;
   }
   y += dy[d];
   x += dx[d];
   if(invalid(y, x))return false;
 }
}

int main(){
 int T;
 cin >> T;
 rep(tc, T){
   if(tc != 0)cout << endl;
   cin >> n;

   getline(cin, s[0]);
   rep(i, n){
     getline(cin, s[i]);
   }
   while(1){
     string query;
     getline(cin, query);
     if(query.length() == 0)break;
     cout << endl << query << endl;
     bool found = false;
     rep(y, n){
       rep(x, n){
         rep(d, 8){
           if(s[y][x] == ' ')continue;
           if(ok(query, y, x, d)){
             found = true;
             cout << "(" << y +1<< ',' << x+1<<") - " << D[d] << endl;
           }
         }
       }
     }
     if(!found)cout << "not found" << endl;
   }
 }
}