## 707 - Robbery

Moderator: Board moderators

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

### 707

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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

### 707 - Robbery

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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
As I have asked before, anyone who did the problem can u explain it to me?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions
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
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

### 707 "Robbery"

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
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Contact:

### 707 : Robbery

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 707 : Robbery

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

[quote="

andrej2000pp
New poster
Posts: 1
Joined: Tue Aug 30, 2005 7:55 pm
Location: Prilep,Macedonia

### 707 Robbery

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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
New poster
Posts: 1
Joined: Mon Nov 08, 2010 4:28 am

### Re: 707 - Robbery

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
New poster
Posts: 1
Joined: Fri Nov 26, 2010 5:11 pm

### Re: 707 - Robbery

jester_vg086 wrote: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
New poster
Posts: 1
Joined: Fri Nov 26, 2010 6:18 pm

### Re: 707 - Robbery

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.

``````