707 - Robbery

[Zhou Yiyan@SHU]

The problem description says, "Assuming that the robber can move at most one unit per time step". Then could the robber stay at one place for some time steps if there is no other way to go?

If I find two available routes for robber to move, should I output "Nothing known"?

B.T.W
[cpp]3 1 4
3
1 1 1 2 1
2 1 1 1 1
4 2 1 3 1
[/cpp]
what is the output?

[likhan]

I did not understand the problem definition well. Is standing in one place in the next time frame a possible move. If we cannot determine a unique path in the middle but there exist a path shall we output the unique paths of the two end or "Nothing Known". And so on. Can anyone explain me the problem better.

[likhan]

As I have asked before, anyone who did the problem can u explain it to me?

Thanx in advance

[Adrian Kuegel]

Is standing in one place in the next time frame a possible move. If we cannot determine a unique path in the middle but there exist a path shall we output the unique paths of the two end or "Nothing Known".

yes, standing in one place in the next time frame is a possible move. And you should output all parts of the path you can determine, therefore you should only print "Nothing Known" if there is no timestep with a known place of the robber.

[likhan]

Thanx Adrien. If the first time step

######
#00#0#
######
######

2nd

######
#0000#
#0000#
######

here # stands for place which was monitored by inspector robstop and 0 where there was no monitoring.

what'll be the output.

thanx

[Rinoaheartilly]

I'm very sorry but I have a severals questions about problems. First what is L, T, R,B? I know that they are left, top, right, bottom. But left, right... to what? The problem said that the town is in rectangular shape, and the top left corner is(1,1) and the bottom right corner is (W,H). So go back to my question what are left, right , top , bottom refer to? Moreover what is "t"? Does it have anything to do with this problem? I am very sorry if I am not supposed to post questions here? Thanks

[Guest]

Hello,
The problem statement does not seem very clear to me. Can anyone answer the following questions?

1. "..the robber can move at most one unit per time step", does this movement include diagonal movements as well?
2. The output will be "The robber has escaped.", only when for a specific timestep, all the blocks are blocked, or the robber cannot reach the free block(s) from possible positions of previous timestep.
3. What should the output be for a timestep when there are more than one possible location of the robber?
4. When to output "Nothing known."?

Any test case will be greatly appreciated.
Thanks.

[mf]

Hi, I just solved this problem. (got a few WAs for a spelling mistake )

[quote="

[andrej2000pp]

Can someone please tell me what's wrong with my code? I get WA.

Code: Select all

#include<stdio.h>
int m,n,t,mat[101][101][101],poznato[101],mozi[101],iii[101],jjj[101];
const int dx[]={0,0,0,-1,1};
const int dy[]={0,1,-1,0,0};
void memo(int i,int j,int v);
void najdipat(int i,int j,int v);
main()
{
      int tt,l,r,tp,b,i,j,k,br,test,mozii,da;
      test=0;
      while(1)
      {
       scanf("%d %d %d",&m,&n,&t);
       if(m==0 && n==0 && t==0) break;
       test++;
       
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         for(k=1;k<=t;k++)
          mat[i][j][k]=-1;
       for(i=1;i<=t;i++) {mozi[i]=-1;poznato[i]=0;}
       scanf("%d",&br);
       if(br>0)
       {
       for(i=1;i<=br;i++)
       {
        scanf("%d %d %d %d %d",&tt,&l,&tp,&r,&b);
        for(j=l;j<=r;j++)
         for(k=tp;k<=b;k++)
          mat[j][k][tt]=0;
       }
       printf("Robbery #%d:\n",test);
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         if(mat[i][j][1]==-1)
         {
          mat[i][j][1]=3;
          memo(i,j,1);
          }
       for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
         if(mat[i][j][t]==3)
         {
          mat[i][j][t]=1;
          najdipat(i,j,t);
          mat[i][j][t]=3;
          }
       da=1;
       for(i=1;i<=t;i++)
        if(!poznato[i]) { da=0; break;}
        
         if(!da) printf("The robber has escaped.\n");
        else{
       mozii=0;
       for(i=1;i<=t;i++)
        if(mozi[i]==1) mozii++;
       if(mozii==0) printf("Nothing known.\n");
       else for(i=1;i<=t;i++) if(mozi[i]) printf("Time step %d: The robber has been at %d,%d.\n",i,iii[i],jjj[i]);
       }
       }
       else{
            if(m==1 && m==n) for(i=1;i<=t;i++) { printf("Time step %d: The robber has been at 1,1.\n",i);}
            else printf("Nothing known.\n");
            }
       }
}
void memo(int i,int j,int v)
{
     int ii;
     if(v<t)
     {
     for(ii=0;ii<=4;ii++)
     {
     if((i+dx[ii])>=1 && (i+dx[ii])<=m && (j+dy[ii]>=1) && (j+dy[ii]<=n))
     {
      if(mat[i+dx[ii]][j+dy[ii]][v+1]==-1)
      {
       mat[i+dx[ii]][j+dy[ii]][v+1]=3;
       memo(i+dx[ii],j+dy[ii],v+1);
      }
      }
     }
     }
     else{
          mat[i][j][v]=3;
          }
}
void najdipat(int i,int j,int v)
{
int ii,jj,kk;
  if(v>1)
  {
    for(ii=0;ii<=4;ii++)
     {
     if((i+dx[ii])>=1 && (i+dx[ii])<=m && (j+dy[ii]>=1) && (j+dy[ii]<=n))
     {
      if(mat[i+dx[ii]][j+dy[ii]][v-1]==3)
      {
       mat[i+dx[ii]][j+dy[ii]][v-1]=1;
       najdipat(i+dx[ii],j+dy[ii],v-1);
       mat[i+dx[ii]][j+dy[ii]][v-1]=3;
      }
      }   
     }
    }
  else {
     for(kk=1;kk<=t;kk++)
       for(ii=1;ii<=m;ii++)
        for(jj=1;jj<=n;jj++)
         if(mat[ii][jj][kk]==1)
         {
          if(!poznato[kk]) 
           {
           mozi[kk]=1;
           poznato[kk]=1;
           iii[kk]=ii;
           jjj[kk]=jj;
           }
          else
          {

              if(ii!=iii[kk] || jj!=jjj[kk]) mozi[kk]=0;
          }     
         }
       }
}

[serur]

The map corresponding to the first testcase:

At time 1:

Code: Select all

####
####
####
###o
oooo

At time 4:

Code: Select all

###o
####
####
####
oooo

Why he can't stay at X:

Code: Select all

###o
####
####
####
Xooo

all the time?

[jester_vg086]

what is the output for this input?

Code: Select all

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5
0 0 0

[guissmo]

what is the output for this input?

Code: Select all

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5
0 0 0

Thank you for this input! Finally got AC!

[noobcake]

Here are some test cases, in case they're needed.
Input:

Code: Select all

5 5 3
2
1 1 1 4 4
2 2 2 5 5

5 5 3
2
1 1 1 4 5
2 2 1 5 5

10 1 10
1
1 2 1 10 1

10 1 5
3
1 2 1 10 1
3 1 1 2 1
3 4 1 10 1

10 1 5
3
1 2 1 10 1
4 1 1 2 1
4 4 1 10 1

100 100 100
0

1 1 3
0

1 1 1
1
1 1 1 1 1

10 1 7
8
1 2 1 10 1
3 1 1 2 1
3 4 1 10 1
6 1 1 1 1
6 3 1 3 1
6 5 1 10 1
7 1 1 2 1
7 4 1 10 1

1 2 2
1
2 1 1 1 1

5 5 5
22
1 1 1 1 2
1 1 4 1 4
1 2 1 5 5
2 1 1 1 5
2 2 1 2 2
2 2 4 2 5
2 3 1 4 5
2 5 1 5 4
3 1 1 2 5
3 3 1 3 2
3 3 4 3 5
3 4 1 4 5
3 5 2 5 5
4 1 2 1 5
4 2 1 3 5
4 4 1 4 2
4 4 4 4 5
4 5 1 5 5
5 1 1 1 4
5 2 1 4 5
5 5 1 5 2
5 5 4 5 5

0 0 0

Output:

Code: Select all

Robbery #1:
Nothing known.

Robbery #2:
The robber has escaped.

Robbery #3:
Time step 1: The robber has been at 1,1.

Robbery #4:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 2,1.
Time step 3: The robber has been at 3,1.

Robbery #5:
Time step 1: The robber has been at 1,1.
Time step 4: The robber has been at 3,1.

Robbery #6:
Nothing known.

Robbery #7:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 1,1.
Time step 3: The robber has been at 1,1.

Robbery #8:
The robber has escaped.

Robbery #9:
Time step 1: The robber has been at 1,1.
Time step 2: The robber has been at 2,1.
Time step 3: The robber has been at 3,1.
Time step 7: The robber has been at 3,1.

Robbery #10:
Time step 2: The robber has been at 1,2.

Robbery #11:
Time step 1: The robber has been at 1,3.
Time step 2: The robber has been at 2,3.
Time step 3: The robber has been at 3,3.
Time step 4: The robber has been at 4,3.
Time step 5: The robber has been at 5,3.