OJ Board

Code: Select all

Removed after AC

Code: Select all

input:
====
4
3
1 1
3 3
2
2 3 S
2 2 W
3
1 1
3 3
0
3
1 1
1 1
0
30
1 1
30 30
0

Code: Select all

3
6
1
51542064 /* This output is wrong due to 32-bit integer */

Code: Select all

3
6
1
30067266499541040

Code: Select all

3
3
1 1
3 3
3
2 3 S
2 2 W
1 1 E
3
2 1
2 3
0
10
5 5
8 6
3
5 5 N
5 6 E
8 5 E

Code: Select all

1
1
3

Code: Select all

#include<stdio.h>
long long sa[39][39],A[39][39][3],i,j,x,y,X,Y,a,b,test,n,m;
char temp[10];


int main()
{

scanf("%lld",&test);

while(test--)
{

scanf("%lld",&n);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{sa[i][j]=0;
 for(a=0;a<2;a++)
	 A[i][j][a]=0;
}

scanf("%lld",&x);
scanf("%lld",&y);
sa[x][y]=1;
scanf("%lld",&X);
scanf("%lld",&Y);
//scanf("%I64d %I64d",&X,&Y);

scanf("%lld",&m);
for(i=0;i<m;i++)
{
scanf("%lld %lld %s",&a,&b,temp);
if(temp[0]=='S')
A[a-1][b][0]=1;
else if(temp[0]=='W')
A[a][b-1][1]=1;
else if(temp[0]=='E')
A[a][b][1]=1;
else if(temp[0]=='N')
A[a][b][0]=1;

}


for(i=x;i<=X;i++)
for(j=y;j<=Y;j++)
if(sa[i][j]!=0)
{
if(A[i][j][0]==0)
sa[i+1][j]+=sa[i][j];
if(A[i][j][1]==0)
sa[i][j+1]+=sa[i][j];
}
printf("%lld\n",sa[X][Y]);

}


return 0;
}

Code: Select all

#include <stdio.h>
#include <assert.h>

#define MAX_N 30

int main(void)
{
  int C, N, Ax, Ay, Bx, By, W;
  int x, y;

  /* whether an intersection is blocked from W or S */
  int blockW[MAX_N+1][MAX_N+1], blockS[MAX_N+1][MAX_N+1];
  char dir;

  unsigned long long ways[MAX_N+1][MAX_N+1];

  scanf("%d", &C);
  while (C-- > 0) {
    scanf("%d %d %d %d %d", &N, &Ax, &Ay, &Bx, &By);
    
    assert(1 < N && N <= 30 && Ax <= Bx && Ay <= By);
    for (x = 1; x <= N; x++) {
      for (y = 1; y <= N; y++) {
	blockW[x][y] = blockS[x][y] = 0;
      }
    }
    scanf("%d", &W);
    while (W-- > 0) {
      scanf("%d %d %c", &x, &y, &dir);
      switch (dir) {
      case 'N':
	blockS[x][y+1] = 1;
	break;
      case 'S':
	blockS[x][y] = 1;
	break;
      case 'E':
	blockW[x+1][y] = 1;
	break;
      case 'W':
	blockW[x][y] = 1;
	break;
      default:
	assert(0);
      }
    }

    ways[Ax][Ay] = 1;
    for (y = Ay+1; y <= By; y++) {
      ways[Ax][y] = !blockS[Ax][y]; 
    }

    for (x = Ax+1; x <= Bx; x++) {
      for (y = Ay; y <= By; y++) {
	ways[x][y] = (blockW[x][y]) ? 0 : ways[x-1][y];
	if (y > Ay && !blockS[x][y]) {
	  ways[x][y] += ways[x][y-1];
	}
      }
    }

    printf("%lld\n", ways[Bx][By]);
  }

  return 0;
}

Code: Select all

1
3
1 1
3 3
2
2 3 S
3 2 W