Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include "iostream" 
using namespace std;
int b[1000][3],k,ge,m,n;  
bool a[102][102],pp;
void dfs(int x,int y,int k0){
  int i,p,q,f;
  p=b[k0][0];q=b[k0][1];f=b[k0][2];
  if(pp==1) return ;
  if(k0==k) {ge++;pp=1;return ;}
  if(p==q){
    if(f==1 && y+q <= n){
      for(i=0; i <= q; i++)
        if(a[x][y+i]==1) break;
        if(i==q+1) dfs(x,y+q,k0+1);}
    if(f==2 && y-q >= 1){
      for(i=0; i <= q; i++)
        if(a[x][y-i]==1) break;
        if(i==q+1) dfs(x,y-q,k0+1);}
    if(f==3 && x-q >= 1){
      for(i=0; i <= q; i++)
        if(a[x-i][y]==1) break;
        if(i==q+1) dfs(x-q,y,k0+1);}
    if(f==4 && x+q <= m){
      for(i=0; i <= q; i++)
        if(a[x+i][y]==1) break;
        if(i==q+1) dfs(x+q,y,k0+1);}
  }
  else {
    if(f==1 && y+q <= n){
      for(i=0; i <= q; i++)
        if(a[x][y+i]==1) break;
        if(i==q+1) dfs(x,y+q,k0+1);}
    if(f==2 && y-q >= 1){
      for(i=0; i <= q; i++)
        if(a[x][y-i]==1) break;
        if(i==q+1) dfs(x,y-q,k0+1);}
    if(f==3 && x-q >= 1){
      for(i=0; i <= q; i++)
        if(a[x-i][y]==1) break;
        if(i==q+1) dfs(x-q,y,k0+1);}
    if(f==4 && x+q <= m){
      for(i=0;i <= q; i++)
        if(a[x+i][y]==1) break;
        if(i==q+1) dfs(x+q,y,k0+1);}
    if(f==1 && y+p <= n){
      for(i=0; i <= p; i++)
        if(a[x][y+i]==1) break;
        if(i==p+1) dfs(x,y+p,k0+1);}
    if(f==2 && y-p >= 1){
      for(i=0; i <= p; i++)
        if(a[x][y-i]==1) break;
        if(i==p+1) dfs(x,y-p,k0+1);}
    if(f==3 && x-p >= 1){
      for(i=0; i <= p; i++)
        if(a[x-i][y]==1) break;
        if(i==p+1) dfs(x-p,y,k0+1);}
    if(f==4 && x+p <= m){
      for(i=0; i <= p; i++)
        if(a[x+i][y]==1) break;
        if(i==p+1) dfs(x+p,y,k0+1);}
  }
}
int main(){
  int i,j,t,sum;
  char c;
  cin >> t;
  while(t && t--){
    cin >> m >> n;
    for(i=0; i<= 101; i++)
      for(j=0; j <= 101; j++) a[i][j]=1;
      for(i=1; i <=m; i++)
        for(j=1; j <=n; j++) cin >> a[i][j];
        k=0;
        while(cin >> b[k][0] >> b[k][1]){
          if(b[k][0]==0 && b[k][1]==0) break;
          cin >> c;
          if(c=='R') b[k][2]=1;
          else if(c=='L') b[k][2]=2;
          else if(c=='U') b[k][2]=3;
          else if(c=='D') b[k][2]=4;
          k++;}
        sum=0;
        for(i=1; i <= m; i++)
          for(j=1; j <= n; j++){
            if(a[i][j]==0){
              ge=0;pp=0;
              dfs(i,j,0);
              sum+=ge;}
          }
          cout << sum << endl;}
  return 0;
}