707 - Robbery
Moderator: Board moderators
-
- 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?
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?
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.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".
-
- 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
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.
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.
Re: 707 : Robbery
Hi, I just solved this problem. (got a few WAs for a spelling mistake
)
[quote="

[quote="
-
- 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;
}
}
}
}
The map corresponding to the first testcase:
At time 1:
At time 4:
Why he can't stay at X:
all the time?
At time 1:
Code: Select all
####
####
####
###o
oooo
Code: Select all
###o
####
####
####
oooo
Code: Select all
###o
####
####
####
Xooo
-
- 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
Re: 707 - Robbery
Thank you for this input! Finally got AC!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
Re: 707 - Robbery
Here are some test cases, in case they're needed.
Input:
Output:
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
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.