928 - Eternal Truths

[mrahman]

I am getting WA several times using BFS with a distance array d[301][301][3]
Can anyone put some input/output.

Thanks in advance

[little joey]

Are you sure you're not jumping over a wall when performing double and tripple steps? Apart from that, I can see no pitfalls in this problem.

Code: Select all

1
3 2
S.
##
.E
 

The answer is 'NO'.

[mrahman]

Hi little joey

I have checked those already. But fail to get AC. Here is my search function

Code: Select all

#define SIZE 100001
#define INF 1000000000
int dr[]={1,0,-1,0};
int dc[]={0,1,0,-1};
int d[301][301][3],n,m,sx,sy,tx,ty,st,end;
char grid[301][301];
typedef struct node
{
	int x,y,cost,dir;
}node;
node Q[SIZE];
int valid(int r,int c)
{
	if(r<0 || r>=m || c<0 || c>=n)return 0;
	return 1;
}
void enq(node p)
{
	Q[end++] = p;
}
void deq(node *p)
{
	*p = Q[st++];
}
int search(int r,int c)
{
	node tmp,temp;
	int i,j,k,cx,cy,len,inv,_min;
	for(i=0; i<m; i++)
	for(j = 0; j<n; j++)
	for(k = 0; k<3;k++)
	    d[i][j][k] = INF;
		
                d[r][c][0] = 0;
	st = end = 0;
	tmp.x = r;
	tmp.y = c;
	tmp.dir = 0;
	tmp.cost = 0;
	enq(tmp);	
	while(st != end)
	{
		deq(&tmp);
		len = tmp.dir + 1;
		for(i=0;i<4;i++)
		{
			cx = tmp.x;
			cy = tmp.y;
			inv = 0;
			for(j=0;(j<len) && !inv;j++)
			{
				cx = cx + dr[i];
				cy = cy + dc[i];
				if(valid(cx,cy) && grid[cx][cy]  == '.');
				else inv = 1;
			}
			if(!inv)
			{
				if(d[cx][cy][len%3]>d[tmp.x][tmp.y][tmp.dir] + 1)
				{
					d[cx][cy][len%3]=d[tmp.x][tmp.y][tmp.dir] + 1;
					temp.x = cx;
					temp.y = cy;
					temp.dir = len%3;
					temp.cost = d[tmp.x][tmp.y][tmp.dir] + 1;
					enq(temp);
				}
			}
		}
	}
	_min = INF;
	for(i=0;i<3;i++)
		if(d[tx][ty][i]<_min)_min = d[tx][ty][i];
	return _min;
}

Can you check where is my mistake Plz

Thanks in advance

[Darko]

Increase queue size - there might be 300x300x3 possibilities. I just checked an empty board and my q.end went over 100000.

[little joey]

Hi little joey

I have checked those already. But fail to get AC. Here is my search function

Code: Select all

<SNIP>

Can you check where is my mistake Plz

Thanks in advance

I could, but I find it very hard to read code that can't be compiled, because it isn't complete.
The only thing I noticed is that your queue size is too small (100000, when you want to store 300*300*3 items).

[mrahman]

Thanks to little joey and Darko,

I just change my Queue size to 300000 and get AC. At first I didn't think about this amount of size.

Thank you anyway

[shihabrc]

Hi all,

i'm getting WA in 928 with my BFS code. Can some1 provide hlp plz (suggetions,i/o......)

Code: Select all

#include <stdio.h>
#include <queue>
#include <string.h>

using namespace std;

#define MAXN 300
#define _min(a,b) (a) < (b) ? (a) : (b)

typedef struct state_
{
	int r,c,nm;
} state_;

int row,col;
char maze[MAXN + 1][MAXN + 1];
bool visited[MAXN + 1][MAXN + 1][4];
int d[MAXN + 1][MAXN + 1][4];
int move[][2] = 
{
	{1,0},
	{-1,0},
	{0,1},
	{0,-1}
};


void BFS(state_ s)
{
	int k,i,nr,nc,nm;
	state_ u,next;
	queue <state_> Q;
	bool found;

	memset(visited,false,sizeof(visited));
	while(!Q.empty()) Q.pop();Q.push(s);
	visited[s.r][s.c][1] = true,d[s.r][s.c][1] = 0;

	while(!Q.empty()) 
	{
		u = Q.front();
		Q.pop();

		for( i = 0; i < 4; i++ )
		{
			nr = u.r + move[i][0] * u.nm;
			nc = u.c + move[i][1] * u.nm;
			nm = (u.nm % 3) + 1;
			
			if( nr >= 0 && nc >= 0 && nr < row && nc < col)
			{
				if( u.r == nr )
				{
					found = false;
					for( k = u.c; k <= nc; k++ ) 
						if( maze[u.r][k] == '#' ){ found = true;break;}

					if( found ) continue;
				}

				else if( u.c == nc )
				{
					found = false;
					for( k = u.r; k <= nr; k++ )
						if( maze[k][u.c] == '#' ){ found = true;break;}

					if( found ) continue;
				}
			}
				
			if( nr >= 0 && nr < row && nc >= 0 && nc < col && !visited[nr][nc][nm] && maze[nr][nc] != '#' )
			{
				visited[nr][nc][nm] = true;
				next.r = nr,next.c = nc,next.nm = nm;
				d[nr][nc][nm] = d[u.r][u.c][u.nm] + 1;
				Q.push(next);
			}
		}
	}
}

int main()
{
	int T,i,j,sr,sc,er,ec;
	state_ s;
	
	//freopen("C:\\4.txt","r",stdin);

	scanf("%d",&T);
	
	while(T)
	{
		T--;
		
		scanf("%d %d",&row,&col);
		while(getchar() != '\n');
		for( i = 0; i < row; i++ ) 
		{
			gets(maze[i]);
			
			for( j = 0; j < col; j++ ) if( maze[i][j] == 'S' ) { sr = i,sc = j;break; }
			for( j = 0; j < col; j++ ) if( maze[i][j] == 'E' ) { er = i,ec = j;break; }
		}

		s.r = sr,s.c = sc,s.nm = 1;	
		
		BFS(s);
		
		int sp = ~(1<<31);

		for( i = 1; i <= 3; i++ )
		{
			if( visited[er][ec][i] )
			{
				sp = _min(sp,d[er][ec][i]);
			}
		}

		if( sp != ~(1<<31) ) printf("%d\n",sp);
		else printf("NO\n");
	}

	return 0;
}

[rambo1980]

Shihab vaia, you are probably forgetting that you can not jump past e wall at any time. Although it's not mentioned in the question, i've added it to my code and got AC with .05 seconds.

[mahbub2012]

thanks brianfry713.

Code: Select all

removed

[brianfry713]

Input:

Code: Select all

1
1 10
S........E

AC output: 5

[sonjbond]

why I am getting WA in this simple problem ? Anyone help me
My Code :

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <string.h>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

#define nln        puts("")                         ///printnewline
#define getInt(a)  scanf("%d",&a)
#define Max(a,b,c) max(a,max(b,c))                  ///3 ta theke max
#define Min(a,b,c) min(a,min(b,c))                  ///3 ta theke min

#define FOR1(i,n)  for(i=1;i<=n;i++)
#define FOR0(i,n)  for(i=0;i<n;i++)                 ///looping
#define FORR(i,n)  for(i=n-1;i>=0;i--)
#define ALL(p)     p.begin(),p.end()

#define SET(p)     memset(p,-1,sizeof(p))
#define CLR(p)     memset(p,0,sizeof(p))            ///memset
#define MEM(p,v)   memset(p,v,sizeof(p))

#define READ(f)    freopen(f, "r", stdin)           /// file
#define WRITE(f)   freopen(f, "w", stdout)

#define SZ(c)      (int)c.size()
#define PB(x)      push_back(x)                     ///STL defines
#define MP(x,y)    make_pair(x,y)
#define ff         first
#define ss         second

#define LI         long int
#define LLI        long long int
#define f64        long double
#define PI         acos(-1.0)                        ///PI er value

#define check(n, pos) (n & (1<<(pos)))       ///AND
#define biton(n, pos) (n | (1<<(pos)))       ///OR     }-bit opr.
#define bitoff(n, pos) (n & ~(1<<(pos)))     ///OFF

#define dbg(x) cout <<"Line= "<<__LINE__ <<" ->  "<< #x " = " << (x) << endl;

void CI(int &_x)
{
    scanf("%d",&_x);
}
void CI(int &_x,int &_y)
{
    CI(_x);
    CI(_y);
}
void CI(int &_x,int &_y,int &_z)
{
    CI(_x);
    CI(_y,_z);
}
void CI(int &_a,int &_b,int &_c,int &_d)
{
    CI(_a,_b);
    CI(_c,_d);
}

template<typename T> void getarray(T a[],int b,int e)
{
    for(int i=b; i<e+b; i++) cin>>a[i];
}
template<typename T> void printarray(T a[],int b,int e)
{
    for(int i=b; i<e-1+b; i++) cout<<a[i]<<" ";
    cout<<a[e-1+b]<<endl;
}
template <typename T> T BigMod (T b,T p,T m)
{
    if (p == 0) return 1;
    if (p%2 == 0)
    {
        T s = BigMod(b,p/2,m);
        return ((s%m)*(s%m))%m;
    }
    return ((b%m)*(BigMod(b,p-1,m)%m))%m;
}
template <typename T> T ModInv (T b,T m)
{
    return BigMod(b,m-2,m);
}

const double EPS=1e-9;                       ///constatnts
const int INF=0x7f7f7f7f;

int dr8[8]= {1,-1,0,0,1,-1,-1,1};            ///8 direction move
int dc8[8]= {0,0,-1,1,1,1,-1,-1};
int dr4[4]= {0,0,1,-1};                      ///4 direction move
int dc4[4]= {-1,1,0,0};                      ///or adjacent dir.
int kn8r[8]= {1,2,2,1,-1,-2,-2,-1};          ///knight moves
int kn8c[8]= {2,1,-1,-2,-2,-1,1,2};

struct point
{
    int x;
    int y;
    int jump;
    point(int _x=0,int _y=0,int _j=0) : x(_x),y(_y),jump(_j) {};
} ;
char board[301][301];
int dis[301][301][4];
int R,C;
bool isValid(point p)
{
    if(p.x>=1&&p.y>=1&&p.x<=C&&p.y<=R)
        return 1;
    return 0;
}
int ans;
void bfs(point source)
{
    queue<point> Q;
    Q.push(source);
    dis[source.y][source.x][source.jump]=0;
    while(!Q.empty())
    {
        point currp=Q.front();
        Q.pop();
        //cout<<currp.y<<"     "<<currp.x<<"     "<<currp.jump<<"     "<<dis[currp.y][currp.x][currp.jump]<<endl;
//        if(board[currp.y][currp.x]=='E')
//        {
//            ans= dis[currp.y][currp.x][currp.jump];
//            return;
//        }
        for(int i=0; i<4; i++)
        {
            point nextp=point(currp.x+dr4[i]*currp.jump, currp.y+dc4[i]*currp.jump, currp.jump%3+1);
            if(isValid(nextp)==1)
            {
                int &kola=dis[nextp.y][nextp.x][nextp.jump];
                if(kola==INF)
                {
                    bool obst=0;
                    for(int mv=1; mv<=nextp.jump; mv++)
                    {
                        if(board[currp.y+dc4[i]*mv][currp.x+dr4[i]*mv]=='#')
                            obst=1;
                    }
                    if(obst)
                        continue;
                    kola=dis[currp.y][currp.x][currp.jump]+1;
                    Q.push(nextp);
                }
            }
        }
    }
}

/**UVa 928**/

int main()
{
    //READ("input.txt");
//    WRITE("input.txt");
    int t,i,j;
    CI(t);
    point start,endp;
    while(t--)
    {
        CI(R,C);
        for(int r=1; r<=R; r++)
        {
            getchar();
            for(int c=1; c<=C; c++)
            {
                board[r][c]=getchar();
                if(board[r][c]=='S')
                    start = point(c,r,1);
                if(board[r][c]=='E')
                    endp = point(c,r,0);
                dis[r][c][0]=INF;
                dis[r][c][1]=INF;
                dis[r][c][2]=INF;
                dis[r][c][3]=INF;
            }
        }
        ans=INF;
        bfs(start);
        ans=min(ans,dis[endp.y][endp.x][0]);
        ans=min(ans,dis[endp.y][endp.x][1]);
        ans=min(ans,dis[endp.y][endp.x][2]);
        ans=min(ans,dis[endp.y][endp.x][3]);

        if(ans==INF)
            cout<<"NO"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

Thanks in Advance

[brianfry713]

Input:

Code: Select all

100
11 14
.#####..#..#..
#....####.....
##.......##.##
#..#..##.#..##
....#.#.#####.
.#..###..#.###
##..####.#.##.
#.#.....#.#..S
#.###..##.#...
.##....####E.#
####..#.#..##.
15 15
.###.##......#.
#..#.#.##.#....
##.###.#.#...#.
#.#....#....#..
....##..#..####
.#...###.#.#...
#..##.#.###.##.
...###..##..###
#.....#..#...##
#....S.#..###.#
#..###.#.##.#..
#.#.#...#E####.
.#####.#####.#.
#######..##.##.
#.####..#...#..
8 6
##.##E
.#S.#.
....##
#.#...
#.##.#
#.##.#
....#.
..####
3 13
#####......##
#.S#.#.#.E..#
........#...#
10 20
#.#.#.#.#.#.###..###
##..#..#####.#....#.
#.#...##..#..##.....
......###.#.###..#.#
...#..E...##.#.#.#..
..#..##....##..##...
#.#...##..####....##
###.....##....#.##.S
..#.##.....#...#.##.
#.#.#.##.##...#...##
21 19
.#....##.#..##....#
##....###...#....#.
...#..####.###....#
....#.#.#.#.#.###..
.#.##.###..#.#.####
####.#...#.#.....##
.#.#.####.........#
###.#.#..#..E###..#
...####....#..#.##.
....#..#.#.....#..#
...#.#.......####..
.#.###..#.###..###.
#...###.###...##.#.
#.##.##.##.###.#..#
#.####.####.#.#..#.
#....#.###.####.###
##.##.###.#....##..
#.#..#....##.#.####
#...###.#.#.....###
#.##..##..S..#####.
#####.#.##..#..###.
13 3
###
##.
#..
..#
.#.
.#S
#..
#..
.#E
.#.
.#.
...
#.#
2 21
##....#...##...E##.##
##.S#.##..###..#.#.#.
4 9
...#...#.
#..#S.#.#
..####..#
.E###..#.
6 18
##..###..#..#S#.#.
.#..#.#.#..##.#..E
..##....#.#####..#
#...#..###..#####.
#..#..#..#.#...###
.#####.###....##..
5 20
##...#.##########...
##E..###.##.##..####
######S############.
#....##.##.......##.
.##.##.###...#####..
7 19
.##.#..#E.##.##....
..#S#..#...##.##...
.#..####.....#..###
#.....##.#....#..#.
.###..#######...#.#
####....#.#.###....
.##.######.#..#...#
5 12
#....##.#...
...##..#.#.#
#.#####S..##
.#.##...##..
.#.#E##.....
14 14
..##.#.####...
##.###...#.#..
#.....###..#..
.#..E####.#.#.
..##...##.##..
##.#.#..#.#..#
#.S##.#.#..#.#
.#..##..#...#.
#..####..##.##
..##..#.#..###
....###.###..#
#.#.###.####..
##.#.#..#.####
....#..##..#..
14 4
#..#
....
#.#.
#..#
#S##
..##
.###
..#.
#...
....
#.#E
#..#
.#.#
..##
4 21
####S...#.#.#######.#
...#.####.#####...#.E
.....#...#.#........#
..####.#...##.###.###
12 21
..#...#..###...S##.#.
.#.......##.###.#.##.
#..##.##...#.#.#.#..#
#.####..#...#.#.###..
##..#..######.#.#....
..#.##..##.#...##..#.
..#.#...#####.#.#..#.
.#####....##.###....#
....##..##.##..#.#.#.
....##....###..###.#.
.#.#E#.####.....###.#
###.###.....#.###.##.
12 11
####.###..#
###..#.#...
.##..#.#S.#
#..###..##.
#.#.####..#
E..##...#.#
.##...#.##.
.........##
.####.#..#.
#....###...
.#.#.####.#
#.#.####.#.
20 15
#.#...#..#.....
#####.#..##....
#.##.##....#.#.
##....#......##
##...#...####.#
.#...##...#.#..
####..#########
..###.#.#.###.#
#.#E...#..#..#.
..#...#.##.#...
.....####..##..
.##.###S.#.#.##
#...#.##.#....#
####.###.####.#
##.#.....###...
...#.####.#..##
..##.#.#.##.###
...#...#....#..
.##....#...##.#
...#...#.###.#.
19 17
.#.#.##E##..#.#..
.#..#..##.#.#.###
.#..#.#.####.....
#.##.#....#S....#
#..##.#...#.#..#.
...#......######.
.##..#.#...#..#.#
##.#.#.##.#..####
..##..#.#.#######
###.#..######..#.
#..##..#.#..#.##.
.###.#..#.##.##..
#.#.#...#####.#.#
###....#.##......
#.######.#......#
...#.##..###..##.
##.###...#..#.#.#
####..#...#...#.#
#....###.#.......
17 7
#.#.##.
#.#.#.#
#.S##..
.######
....###
##...##
#.##.#.
..#....
#.#...#
..####.
.#...##
##.#...
E#####.
.#.#.##
.#..#.#
..##..#
#..#...
18 2
..
#.
.#
.#
##
#.
S.
.#
#.
#.
##
.#
.#
##
E#
##
.#
.#
6 19
..#..##.#.#......#.
.##.#..#...#.##S#.#
....##...#####..##.
..###.##.#.###..###
#..##.#.#...#####.#
...#...##.#..E#.#.#
5 19
#...#S#.###...#...#
..#.###..###...####
..####.#.#..##E.#.#
#####.#..##...#..##
#...#.####.###..##.
15 20
..##.###.#.##..##..#
##.....#.######...##
....##.#.#.###...#.#
#######..###.......#
.####......#..#.##..
#.#.#.#.##.####...#.
##......##.#..#.###.
#.....#.###.#.###..#
.#.#...#...#.#.#....
..###.#.#..####..#..
.#.###...#.##.####..
#..E......#....#.#.#
.##.#..#....##..#.#.
###.S#.##.#...#.###.
....####.....#..##.#
15 18
#.###.#.###.#.#...
.##.######..#.#.##
###.####.E.#..###.
##.###....#..#....
........##.#...#..
###..#.#.####.#.#.
#####...##.....###
#...#.####...#.##.
..##....#..#..##.#
..##...#.###.#..#.
#.###.####S.#####.
#.#..#.##..##.##.#
..#.#..#......#.#.
.#.#.##..#.#.#....
###.#.#.####..##..
20 11
......#..#.
...#.###.##
#.##.####..
.###.##....
########.##
.#..#..#..#
......#.#S.
#....##.#.#
.##.###...#
#.#....####
.......#..#
.####...#.#
#.#.##.#E#.
###..###..#
..#.##.##..
##...#.....
##.##..##..
####.#.#..#
##.####.###
.######.#..
8 16
.##.#.##.E#.####
#.#..S.##.##.###
##........#...##
##..####.#.##.#.
#.#...##..######
#..#...#.###.#..
#...#...#.##.###
###...#..#...##.
17 13
....##.##.#..
##..#.#.##...
..##...##.###
..#####..#...
....###.#.#..
..#...#...#.#
.#....###.###
####....###..
.S..#..###.#.
.....#.##...#
#...##.#...#.
..#.#....#.##
..####...#.##
.....##..#.##
#..#..#..#...
#.##..##..#.#
.#.#E...#####
11 12
#.#..#.#...#
#..#.....#..
#...##.#.#.#
####.###..#.
###.#.#S....
..#.....##..
#....##.##.#
#.#...####..
#..#.#..#.#.
..#.E.....##
#.#..##....#
4 15
..#.##...#####.
#.####.....#E.#
##.#S.#.##.##..
..#.##..#......
12 9
.##.#.###
..#..###.
#.#..##..
##...##.#
...####..
#.#...#.#
#....#...
..#.#.##.
.S.######
##.####.#
##...##.E
....#.#.#
3 16
.####.###.....E.
.######.##.#.###
####.##.S#.#..##
2 8
.#E###.#
#.#.##.S
19 4
#.#.
#..#
...#
..##
#.##
###.
###.
##.#
..#.
#.##
#.##
#.##
#S.#
E...
.###
#.#.
##..
#..#
#.##
3 14
##.#..#..##..#
##.#.##.#.#S#.
.....#.#E..#..
17 3
#.#
###
.##
...
.#.
#S#
.##
#..
#.#
#.#
...
E..
..#
##.
..#
##.
...
5 5
..#..
.##..
##.##
S.#.#
#E...
18 19
..###.#.##.#...##..
#...#..#.###.######
.###.#.###.###.###.
#...#..#..#...#.##.
##..#..#..#..##E#..
##..####.#####....#
.#...#.#...###..#..
#..#..#.#.####.##..
##.....##.#...#.#.#
.....#####..###....
..#.####....##.#..#
..#.##...###.#..#..
.####....##.#.....#
###....#S..##.#...#
####.#.#.....#.#...
...#...##..#.#.#...
#.#.##.###.#.#..##.
#.#....#..#....#..#
2 6
....S#
.E####
8 14
#.#S..##E....#
##.#.##.##.#..
......##.###..
##.#.####.....
.##.#.#..#.#..
##.#.#.#..#.#.
######.##...##
..#...##..####
21 18
#...#...#.#.###..#
##.#.#...E.#.#.#..
.#....#....#..#...
.###.##.#.....###.
...###S..####..#.#
#..#..######...#..
#.....#...##.##...
#..#..####....##..
#...#.....####..##
#..#.#.#...#...##.
...#....##.#...###
#....###..#...##..
.#...###..#.##...#
..##.#.#..##...#.#
#.#.##.###..##.###
#.#..#.#.#####.#.#
#########.#..##...
...#...#.##.#....#
..#.#.#...#.#.###.
.....###...#.###.#
.###.#..#..#...###
7 21
#..#..##.###.#.....##
#.##.#...#.##.....###
#.#.#.#.##..#.###.#.#
#..##..#..##..#.#..##
#..#.##..#S####..E#.#
##.#...##.#.#.##.#..#
..#.#..##.#..###..##.
17 13
#..#####....#
.#.##.###.###
.##.###.##.##
#####.#.E##.#
.#...#....#.#
###.##.##..##
#.##..###.S#.
#..##.#####..
.##.#.#..##.#
....###.#####
.#.#.#.#...##
##..####.##..
#####.#..#.##
.#..#...#....
#..#..#..####
.#.####..####
##...#..####.
16 8
######.#
..#..##.
###.##E#
...#..#.
...#.###
.#...##.
#S#.#...
.#.##.#.
#..##.#.
###.####
##.#...#
.#..#..#
#####.##
.#......
..###...
##.#.##.
10 6
#.#.#.
#...#.
###.##
..#E..
..#.##
.#.##.
.###S.
.#.#..
###.#.
#..#..
12 5
#####
#.##.
#.##.
...#.
#...#
.#S##
.##..
..#..
.E##.
...#.
#..##
..#.#
8 17
###...##.#.#.##..
...#.##....#.S...
#.#..#.#####.....
##.#.#.###..###..
.#.##.#.#.#.#..##
..###...#.###..##
.#.....#...####.#
#....##.######.E.
6 8
.##.##.#
.###.#E#
S.#####.
#....#.#
#.###.#.
.#..##..
18 13
.###..#######
#...#.#.#....
.#..#####.#.#
#.####.E..#..
###...#######
.#####.##.#.#
...##..#.#...
..S#.########
..###.....##.
..####..#.##.
##.#####.#.#.
##....##.##..
##.#.#####.##
##.#..#.#####
.######.#..##
##.##....###.
.#..#.##.###.
#..#..##.#.#.
6 12
.##..#.##.#E
.##....#....
###...##.#.#
####...#.#.#
S###.##.##.#
..##.##.#..#
10 18
.#######.#.###...#
....##.#.#..#..#.#
#.##..####..####..
#.......##..###.#.
##.E##S.##.#...#.#
.#..###.######....
#####.#...##..##.#
....#.###...#...##
##..#.....###...#.
.#....###..#......
4 6
E#...#
####.#
..S...
###...
13 20
..###.###.#......##.
#########.#.####.#..
...#.#.##..##.##.##.
##.##....#...#.##.##
#.###.#..#..####..##
...#....#..#....#..#
##.##...#...#.#E#.##
#.#.#....#..##.###.#
.##..##..#...#.#.#.#
##.##.##......#...##
.#..##..#####.####.#
.#....######S..#####
##.#..###.#...#####.
18 12
#######.#..#
..#.#.#.#..#
##..#..#..#.
.#...#....#.
..#.##.###.#
.###.####..#
.#.##...####
#.##S.....##
####..###.##
......#.####
#.#.######..
#..#..###..#
#..##..##...
....#####.#.
##.#.##.##.#
E###...#.#..
....#.##...#
.....#.....#
14 8
..####.#
.#.##.S.
#..###..
.#.##.#.
.#...###
#.###...
#..#.#.#
.##.#...
.###.##.
#####..#
##.#.###
..E.###.
.###.#..
........
9 12
##.#..#.#..#
.#...##...##
...######.#.
#.#.#..###..
#.#..####.##
..#.#E#.####
..#.#..#..##
####.###.#.S
......######
14 3
.S.
.##
.##
...
.##
##.
.#.
.#.
###
...
##.
..#
..E
.#.
5 14
.###.##..###.#
...#.#......#.
...#......##..
...##.#E.##...
####..S.#.####
21 11
..###.###.#
..#..#.##.#
#.#..###.#.
.#.###..##.
#.####..#..
####....##.
#..#####.#.
....#...###
##..####.#.
##.##.###..
#...#..#.S.
#..#.......
#..#..#..##
#.#.#.####.
.###...####
.#.###..###
...##.###..
#.#......#.
##..##.E.#.
##..##.....
.###....##.
2 11
.....####..
E##S##....#
16 15
.###....#..####
#..#.#....###.#
.#S###E...####.
###.#...#.#...#
##..#..#......#
#.###.####...##
###...#...##..#
.#..#####...##.
####...###.#.##
..##.##..###.##
.#...####..#.##
..#...###.#..#.
..###..#...#..#
##.##..#....##.
#.####...###.#.
.##.###.#.#.#..
17 18
.S.####.##.######.
#....##..###..##..
#.##..#..#....#.##
.#.....####......#
.####.##.#..####..
...#...###.#.##..#
#.#....##.#.#.#...
#......#...#.#.#..
.#......#.##...##E
....##..#..##.#.##
#..#.###..#.###..#
.#.#..#.########..
#.....#..####....#
#.####.#..####...#
#..#..#....##.####
#.#.#..#......#..#
##...##.##.###.#..
12 18
#..##.#..#######S.
##....###..#....##
##..#...#..#.#.#.#
.##..#....#..###.#
.#..#.#....#..#.##
.#....##.###..##.#
...##...#.##.###..
...##.#....#......
#######.#E#.#..##.
.###..#.#.########
.##..#.#.##...#.#.
###.##.##..###.#.#
8 8
..#.###.
#.##...#
#####.#.
######..
#.##.#..
..#.#SE.
.....##.
##.#.#..
20 13
#.###...##...
#...####..###
....#.....##.
###..#.#..#..
.#.S...##...#
#.#######.#..
.###.....####
#..##..#.....
.#.#.##.#...#
#.##...#...##
#...##..#..##
....#.##.#..#
######..#...#
.#.....##.##.
.#.#....#....
..#..#...###.
#..#.#.#.#.#.
..#.###....##
#.#E###....#.
##.#.##..#...
5 9
######..#
#E...#.#.
.###.#.#.
#.#..#...
.##.S#...
14 2
.#
..
#.
##
##
..
.#
##
.#
#.
SE
##
#.
.#
14 13
##.##.#......
.###.##E#..#.
.##.###.###.#
.#..##.#S###.
.##...##.##..
...#..#.##..#
#..####..##.#
..###.##...##
.###.#.##.#.#
.....##......
####.....#.##
..###...##..#
##....#.#.#.#
.....##..###.
19 11
##....#.###
#...#S.#.#.
#.#.#......
###.##.##..
##.#..#E##.
...###.....
.#....#####
.#####.#.#.
##.###...##
##..##.####
#..##..#..#
#.#.###.#..
.#..#.##.#.
#..##..##..
####..#####
..##...###.
##.....#.#.
.###.##.#.#
..######.##
19 12
...##.#..##.
.#######....
.#..#...##.#
...#...#####
##...#.S####
...#.###.##E
..#..###...#
.#.#..#####.
#..#..##..##
.###.#.####.
#.##.##....#
.#.#..##...#
.##.#..##...
..#.##..##..
.#.#.####...
##.#.#....##
....#.#..###
###...#.#...
###.##..#..#
7 17
.##...#..#####.##
...#.#..#.#.#####
...####..#.#...#.
E...####.###.#.##
..###.#....#.###.
.#.......###.####
####..###.####.#S
15 11
#.#..#..#..
##.#..#..#.
##.##.S...#
.#...#.##..
.####..#..#
#.#.#.##..#
###..#...#.
.#....##.#.
#...#...#.#
##.#.##....
###.##.#..#
.E##..#..#.
.....#.##..
#...###.#..
##..##...##
16 21
.##..#E.#.###.###..##
######..####.#..##..#
.##.###.........#.S..
##.#.###.....##.#.#..
..#.#.###..#......###
#.##.#..##...#.####..
###...#####.####.###.
........##..###.##.##
.##.##..###...###..##
######..#.######..###
....###.##..#..#####.
##.#######.#.##.#.###
.#.######.#####.##.#.
.#....#..##.##.#..##.
#..####.#..####...#.#
..##....##.......###.
17 17
#.######.#..#.#..
###.####.##.#....
.#.##.####.#.##..
#..#.##.###.##.#.
.##.##.#.##....#.
.#.#..##.####...#
#.#....#.#.######
##.###.##...#..#S
#....#...#..#..#.
.#.#####.#..#..#.
...#####...#.####
#####..##..#.#..#
..##.#..##.##....
...#..#....##E###
#.#.##.#.#.#...##
##.#...#.##.##..#
#####.#...#..#..#
21 2
#.
##
..
#.
##
.#
#.
#.
#S
#.
##
##
#.
#.
#.
##
##
..
.E
#.
.#
2 21
##.S.............#.#.
.##...#.##.#.#.#....E
19 16
#######.###.####
..#.#......#..##
.##..#..#.##.#.#
...###..#...#...
...###.#...####.
....#.###..##...
#####....#..#.#.
.##..#...#...###
.##.#....##.###.
###.#.#..E#.#...
..#...######.#..
....#.....#.#.##
.#S########....#
##.#.#.###.#..##
#####.##.###..#.
.#.###.###.##.##
..#.###.###..###
#.#....########.
.#..#..#...#..##
12 10
.#..#.###.
#..####...
.##.###..#
#.#.######
###.##.###
..#.....##
.#...#..#.
##.#..##.#
###...####
#..####.S#
##..####..
....E#####
2 19
####.###.##...##...
...#S...#.#..#.#..E
15 16
..###.#.###....#
.#.#...##.#....#
S..##..#...#####
#.#.....#.#.#.##
#.###.#.#..#..#.
###.#.######.##.
.#....#.#...####
####.#.....#..##
...#....#..#..#.
###....####.##..
###...#.#.......
#.#.#..##..###.#
#.....#....###.#
.....#..##.#####
#...#.#.#E.#.#.#
13 20
#.#..#..#.#.###.###.
.#######..#.#.#...##
.#...##.#.#..#..##..
.###.#.####.###.#S##
#.#...##.#..##..##.#
##..####..#.###.##..
#.##....#.##.....#.#
....#.####.#.#.#.#..
..##...#.#.###.#####
#.#.....###.###.#...
####..#..E....#...#.
####.#..####.#####..
##....##.#...#.###.#
12 8
.###.###
#####..#
###.##..
..#..###
#E.#..#.
.#.#.##.
#####...
.#.##.#.
...#...#
#.#..#.#
#.#.S###
#.####.#
14 12
.#.#.####.#.
#..#..#..#..
#...#..#.##.
##....#.#.#.
###E###..###
..#..##.#.##
.#.........#
........#.#.
.##....#..#.
#.###.##...S
##.#...#....
#..##..##.#.
.#.#.##.##..
.#..####..#.
5 16
##E.##.##.#.###.
.##.#.#...#.....
.#...##.#######.
###.S.####..#...
.#.##..#.#.##...
21 20
..##.#.##.#..##....#
....##.####...##..#.
####.#.####...##..#.
....#...##..#...##.#
#...##...#...##...#.
..##........##..####
#.....###.#####.#.#.
#...#######.#.#.#.#.
##.##.#####.#.##.##.
#.###.#.#####.####.#
....#.....###.#.####
####.#...#.#....####
.###.#........###...
.#.#.E.##.#..#..###.
.#.#..#.#.#.#....#..
...#.#.#.#.###......
..#...##.###.....#.#
S#.#.###..####..###.
###...##...####.##..
..###..#.......##..#
.##.####...#..#..#.#
20 3
.##
##.
###
#.#
###
##.
..#
#..
.#.
...
#.#
#.#
##.
#E#
..#
..#
##.
#.#
.S.
#.#
7 5
#...#
...#.
#.###
.S.#E
...#.
....#
###..
17 6
E##.##
..###.
.##...
##.###
##...#
.###..
####S.
....#.
...#..
...###
#####.
.#.##.
..###.
..###.
...#..
#..#..
...#..
12 19
.##.####..##...#..#
.#.........##...#..
#..#.#..#.#####...#
##.....##..#.#..#..
..#.##.#.#.##...#.#
#..#.#####.....#.E.
.#.##..#.#..##.##..
#..##....##...#..##
..###......#.##...#
###...###.#......#S
.#.##.###...##.....
..#.#.##.##..#...#.
5 15
E.###.#...#.###
##...####...##S
....#.##.#.....
...###.##.#####
.###.####.#.#..
20 5
.....
...##
###..
#..##
..###
S#...
###.#
.....
....#
#..#.
....#
.####
.####
#..##
#.#..
#.##.
#.E..
.#...
...#.
.####
15 5
....#
...##
#..##
....#
..#.#
.###S
.###.
.####
#..#.
..#.#
##.#.
.#..E
.##..
##.#.
..#..
9 18
.......###..#.##..
.####...#.#....#.#
.#####.....###.##.
#..##....####.#...
.###..#.#.##.#####
..######....##.##.
..S.###.##.##.##.#
####.#..E#...#####
###.#..##..#..##..
7 7
.#..#.#
..##...
##.E###
###.##.
..###S#
#.#.##.
#..#.#.
21 13
#.#.#......##
..#..######..
#...#..#..###
.....#.#.####
.###.#.####.#
.##..#.#.#.##
##.#######.##
.####.#....##
##.....######
##.#.##.#...#
##.##.#.#..#.
.#..#####.#.#
.#.##.#...###
.....#.##.##.
..##..#..##..
##.#.#.#.#.#.
.#...##.#.###
E#..S....#.#.
..#.#...#.###
#...##....#.#
....######..#
5 18
.#..#.####.#.#.#.#
..#....##.#.#...#.
##.####..#.###.S##
......E.#.##..##.#
.#.#####..#.#.#...
15 11
#E###.#....
....#.....#
##.#.###.##
.#.####.#.#
...###..#..
#..#....##.
.#..##.#...
#..#...##.#
....#..####
#..#...##..
.###...#.#.
#...#.##.##
##..#...#..
..####S...#
#..........
10 9
S.#......
##....##.
..##..#.#
...#.#.#.
#.....###
#.#.##...
#.#.#.#.#
#####...#
##.E##..#
.#.###...
14 18
.##......##.###..#
##...##.########..
.##...#...##..###.
.#..#..#..###..###
...###....S....##.
....#..####.######
#.....###.###...#.
##.###..#..#..#.#.
##......#.#.##.##.
####..#.####.###..
..####.####..#.###
...#..#.#...#.#..#
.#.##...##.##..#..
..#.#.E.#.#.#.....

AC output:

Code: Select all

NO
NO
NO
7
NO
NO
2
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
2
NO
NO
5
8
NO
NO
NO
NO
NO
3
NO
NO
NO
NO
NO
NO
9
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
6
NO
NO
NO
NO
NO
1
NO
3
1
NO
7
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
8
4
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO