USACO 9 Problem 'obstacle' Analysis

by Rob K.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int maxlenth=15000;

int N,s,e;
int M[110][110];
int startx,starty;
int endx,endy;
bool V[110][110];
int teamx[16000];
int teamy[16000];
int L[110][110];

void input(void){
     char C;
     scanf("%d",&N);
     scanf("%c",&C);
     for (int i=1;i<=N;i++){
         for (int j=1;j<=N;j++){
             scanf("%c",&C);
             if (C=='x') M[i][j]=true;
             else if (C=='A'){
                     startx=i;
                     starty=j;
                 }
             else if (C=='B'){
                         endx=i;
                         endy=j;
                 }
         }void output(int res){
     printf("%d\n",res);
}
inline int del(){
     s=(s+1)%maxlenth;
     return s;
}
inline void add(int x,int y,int level){
     if (!V[x][y]){
         e=(e+1)%maxlenth;
         V[x][y]=true;
         teamx[e]=x;
         teamy[e]=y;
         L[x][y]=level;
     }
}
int solve(void){
     add(startx,starty,0);
     while(s!=e){
         if (V[endx][endy]) return L[endx][endy]-1;
         int t=del();
         int x=teamx[t];
         int y=teamy[t];
         int level=L[x][y];
         for (int i=x-1;i>0;i--){  
             if (!M[i][y]) add(i,y,level+1);
             else break;
         }
         for (int i=x+1;i<=N;i++){
             if (!M[i][y]) add(i,y,level+1);
             else break;
         }
         for (int j=y-1;j>0;j--){
             if (!M[x][j]) add(x,j,level+1);
             else break;
         }
         for (int j=y+1;j<=N;j++){
             if (!M[x][j]) add(x,j,level+1);
             else break;
         }
     }
}
int main(){
     freopen("obstacle.in","r",stdin);
     freopen("obstacle.out","w",stdout);
     input();
     output(solve());
     return 0;
}