## 929 - Number Maze

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 929 - Number Maze

He is correct, I am not sure why you don't believe him. What does flag[j-1]==0 evaluate to if j==0?

lazyboy
New poster
Posts: 17
Joined: Tue Jul 08, 2008 3:19 am

### Re: 929 - Number Maze

sorry , I bilieved him and i used

Code: Select all

``````if(j>0 && flag[i][j-1]==0)

and also,

if(j>0)
if(flag[i][j-1]==0)
``````
but for both the time i got RE.
so i think problem is in another portion.

Is my heapify correct and array size enough?

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 929 - Number Maze

@lazyboy
well after some time debugging i found out what was the reason behind RE. The reason was obviously array limit was not sufficient. but as you already suspected the maximum size can be only 1000 x 1000 = 1000000, which you have already allocated. So I suspected you might be entering the same node more than once in the queue thus crossing the limit. And i was right.

Here is the summary of what i did:

Code: Select all

``while(i!=n && j!=m)(``
i used

Code: Select all

``````while (true) {
temp = a[1].data;
i = a[1].x;
j = a[1].y;
if (i == n - 1 && j == m - 1)
break;
......
``````
and removed the other break statements.

hmm..

lazyboy
New poster
Posts: 17
Joined: Tue Jul 08, 2008 3:19 am

### Re: 929 - Number Maze

i removed my code.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 929 - Number Maze

plz give me some test case, all the board input my program give same but i can not remove WA.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 929 - Number Maze

I got TLE for this problem.... I tried implementing queue as in the previous posts said, but I still got TLE. I think there is something wrong with my code. Can anybody help me ?

Code: Select all

``````#include <stdio.h>
#include <memory.h>
#include <limits.h>

struct CNum
{
int number;
int x, y;
};

struct move
{
int x, y;
};

class CQueue
{
public :
CNum data[1000000];
int front, rear;

inline void push(int dat, int x, int y)
{
data[rear].number = dat;
data[rear].x = x;
data[rear].y = y;
rear++;
}

inline CNum pop()
{
if(front <= rear)
return data[front++];
}

CQueue()
{
clear();
}

inline void clear()
{
front = rear = 0;
}
};

int maze[1000][1000], distance[1000][1000];
CQueue Q[10];
char buffer [50000];

int main()
{
move moves[4], t;
int cases, row, col, i, j, idxmin, row1, col1, metu;
char *ctr;

CNum MNow;

freopen("f.in", "r", stdin);
freopen("f.out", "w", stdout);

moves[0].x = -1;
moves[0].y =  0;
moves[1].x =  1;
moves[1].y =  0;
moves[2].x =  0;
moves[2].y = -1;
moves[3].x =  0;
moves[3].y =  1;

scanf("%i\n", &cases);

while(cases--)
{
for(i = 0 ; i < 10; i++)
{
Q[i].clear();
}
scanf("%i\n%i\n", &row, &col);

for(i = 0; i < row; i++)
{
gets(buffer);
ctr = buffer;
for(j = 0; j < col; j++)
{
while(*ctr == ' ') ctr++;
maze[i][j] = *ctr - '0';
distance[i][j] = INT_MAX;
ctr++;
}
}

row1 = row - 1;
col1 = col - 1;

// BFS
distance[0][0] = maze[0][0];
Q[0].push(maze[0][0],0,0);
idxmin = 0;
metu = 0;
while(!metu)
{
MNow = Q[idxmin].pop();
//printf("%i %i %i\n", MNow.x, MNow.y, MNow.number);
for(i = 0; i < 4; i++)
{
t.x = MNow.x + moves[i].x;
t.y = MNow.y + moves[i].y;
if(t.x >= 0 && t.x < col &&
t.y >= 0 && t.y < row)
{
if(distance[t.y][t.x] > MNow.number + maze[t.y][t.x])
{
if(t.y == row1 && t.x == col1)
{
printf("%i\n", MNow.number + maze[t.y][t.x]);
metu = 1;
break;
}
else
{
distance[t.y][t.x] = MNow.number + maze[t.y][t.x];
Q[distance[t.y][t.x] % 10].push(distance[t.y][t.x], t.x, t.y);
}
}
}
}

if(!metu)
{
// Get Highest Priority
for(i = 0; i < 10; i++)
{
if(Q[i].front != Q[i].rear)
{
idxmin = i;
break;
}
}

for(i = i + 1; i < 10; i++)
{
if( (Q[i].front != Q[i].rear) &&
Q[i].data[Q[i].front].number < Q[idxmin].data[Q[idxmin].front].number)
{
idxmin = i;
}
}
}
}
}

return 0;
}
``````

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

### Re: 929 - Number Maze

WR Help.....
i use simple bfs with 10 queue, bur getting WR....pl help me.

Code: Select all

``````// find bugs,code remove
``````
"Dream Is The Key To Success"

@@@ Jony @@@

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 929 - Number Maze

Could not find any error ,pls help

Code: Select all

``````code removed got acc.... :D
``````

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 929 - Number Maze

Pass this cases and you should get ac:

Code: Select all

``````4
1 1
9
2 2
0 0
0 0
20 20
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
9 9 9 0 0 0 0 0 1 2 3 4 6 7 8 9 0 5 4 3
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 3 5 7 8 9 2 2 2 2 3 4 4 4 4 5 6 7 8 9
0 9 9 8 7 6 9 9 9 9 9 9 9 0 0 0 0 0 9 9
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 2 3 4 5 6 7 8 9 5 3 2 4 5 6 7 8 9 9 6
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
0 0 0 0 0 0 1 1 1 1 2 3 3 3 3 3 4 4 4 4
3 3 3 1 1 1 1 1 3 4 5 6 7 8 9 0 5 4 3 1
22 20
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 3 1 4 6 7 8 9 6 5
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
2 4 0 9 7 5 4 6 7 8 4 2 2 2 2 2 8 9 6 5
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 0 6 7 8
1 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
9 9 9 0 0 0 0 0 1 2 3 4 6 7 8 9 0 5 4 3
1 2 3 4 5 6 7 8 9 9 0 6 4 0 0 0 5 6 7 8
1 4 5 7 8 9 7 5 3 4 6 7 4 0 0 0 4 3 5 9
1 3 5 7 8 9 2 2 0 2 3 4 4 0 0 0 6 4 8 9
0 9 9 8 7 6 9 9 9 9 9 9 9 0 0 0 2 0 9 9
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 0 0 0 0 0 0 3 4 5 4 3 1
1 4 5 7 8 9 7 5 3 4 6 7 4 3 6 8 4 3 5 9
1 2 3 4 5 6 7 8 9 5 3 2 4 5 6 7 8 9 9 6
1 2 3 4 5 6 7 8 9 9 0 6 4 3 2 4 5 6 7 8
0 0 0 0 0 0 1 1 1 1 2 3 3 3 3 3 4 4 4 4
3 3 3 1 1 1 1 1 3 4 5 6 7 8 9 0 5 4 3 1
8 5 9 2 4 5 6 7 8 9 2 1 2 3 4 5 6 8 9 0
1 2 3 4 6 6 8 9 9 0 0 0 0 0 3 4 5 4 3 1
``````
output:

Code: Select all

``````9
0
75
67``````
good luck

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 929 - Number Maze

My code finds the result by applying Dijkstra+Min-priority queue.I think mine's just a straightforward implementation of Dijkstra.I hope,You guy could get this coe easily.This one passed all the input found here,but don't know where is my silly mistake???

Code: Select all

``````//cut after getting accepted
``````
Last edited by Imti on Sat Oct 29, 2011 11:54 pm, edited 1 time in total.

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

### Re: 929 - Number Maze

hey Guys, my code gives wrong output for some test cases. I hope you guys help me finding the bug.
I am using dijkstra algorithm

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
int main ()
{

int test;
cin>>test;

for(int t =0; t <test; t++)
{
int row, col;

cin>>row>>col;

int **cost_maze = new int *[row];
for(int i =0; i <row; i++)
cost_maze= new int[col];

int **maze = new int *[row];
for(int i=0; i<row; i++)
maze= new int [col];

int max =0;

int c =0;
for(int i =0; i <row; i++)
{
for(int j =0; j<col; j++)
{
cin>>cost_maze[j];
max = max + cost_maze[j];
maze[j]= c;
c++;
}
}

if(row==1 && col==1)
{
cout<<cost_maze[0][0]<<endl;
continue;
}

c=0;
vector<vector<int> > edge;

for(int i =0; i<row; i++)
{
for(int j=0; j<col; j++)
{

if(i>0 )
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[i-1][j]);
edge[c-1].push_back(cost_maze[i-1][j]);
}

if(i<row-1)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[i+1][j]);
edge[c-1].push_back(cost_maze[i+1][j]);
}

if(j<col-1)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[j]);
edge[c-1].push_back(maze[j+1]);
edge[c-1].push_back(cost_maze[j+1]);
}

if(j>0)
{
c++;
edge.resize(c);
edge[c-1].push_back(maze[i][j]);
edge[c-1].push_back(maze[i][j-1]);
edge[c-1].push_back(cost_maze[i][j-1]);
}

}
}

max = max*max;

int *value = new int [row*col];
for(int i=1; i<row*col; i++)
value[i]= max;

value[0]= 0;

vector<int> Q(row*col);

for(int i=0; i<row*col; i++)
Q[i]= i;

while(Q.size()!= 0)
{

int min = max+1;
int index=0 ;

int it=0;

for(int i=0; i<Q.size(); i++)
{
if(min> value[Q[i]])
{
min = value[Q[i]];
it = Q[i];
index = i;
}
}

for(int i=0; i<edge.size(); i++)
{
if(edge[i][0]== it && value[edge[i][1]]> value[edge[i][0]] + edge[i][2])
{
value[edge[i][1]] = value[edge[i][0]] + edge[i][2];

}

}

Q.erase(Q.begin()+ index);
}

cout<<value[(row*col)-1 ]<<endl;
}
}

New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

### Re: 929 - Number Maze

I'm getting tle for this problem..I used dijkstra,and tried to implement it with just array,without using STL priority queue,just to get it within time limit,bt unsuccessful..can anyone please help me?What can I do to get it within time??

Code: Select all

``````#include<cstdio>
#include<cstring>
using namespace std;
int check[1005][1005];
int inp[1005][1005];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int dis[1005][1005];
typedef struct{
int x,y,w;
}N;
N queue[1000000];
int main()
{
int r,c,i,j,k,t,xx,yy,start,end,min,pos;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&r,&c);
memset(check,false,sizeof(check));
for(i=0; i<r; i++)
{
for(j=0; j<c; j++) scanf("%d",&inp[i][j]);
}
for(i=0; i<r; i++)
{
for(j=0; j<c; j++)
{
dis[i][j]=2474836;
}
}
N s,p,s1,temp;
queue[0].x=0;queue[0].y=0;queue[0].w=inp[0][0];
dis[0][0]=inp[0][0];
start=end=0;
end++;
while(start<end)
{
min=queue[start].w;
pos=start;
for(j=start+1; j<end; j++)/*find the smallest element,and swap it with start pos element*/
{
if(min>queue[j].w)
{
min=queue[j].w;
pos=j;
}
}
temp=queue[pos];
queue[pos]=queue[start];
queue[start]=temp;
s=queue[start];
check[s.y][s.x]=true;
if(s.y==r-1 && s.x==c-1) break;
for(i=0; i<4; i++)
{
xx=s.x+dx[i];
yy=s.y+dy[i];
if(xx<0||yy<0||xx>c-1||yy>r-1) continue;
if(check[yy][xx]==true) continue;
if(dis[yy][xx]>dis[s.y][s.x]+inp[yy][xx])
{
dis[yy][xx]=dis[s.y][s.x]+inp[yy][xx];
}
queue[end].x=xx;queue[end].y=yy;queue[end].w=dis[yy][xx];
end++;
}
start++;
}
printf("%d\n",dis[r-1][c-1]);
}
return 0;
}
``````

New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

### Re: 929 - Number Maze

Can anyone please help me to get in runtime for this problem?What can I do to get it in runtime?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 929 - Number Maze

Searching through the entire queue to find the minimum value is much slower than just using a priority_queue.
Check input and AC output for thousands of problems on uDebug!