2012-04-22 10:17:10Morris
[UVA] 929 - Number Maze
/**********************************************************************************/
/* Problem: d793 "929 - Number Maze" from UVa ACM 929 */
/* Language: C (1909 Bytes) */
/* Result: AC judge by zeroserver@ZeroJudge */
/* Author: morris1028 at 2010-09-22 11:43:39 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MaxValue 32767
#define Size 1000
char Map[Size][Size];
short Dis[Size][Size];
int T, N, M, a, b;
int Sx, Sy, Gx, Gy, L;
struct Heap
{
short x, y, F;
}Heap[1000000], Temp;
/*Heap以下*/
void Swap(int P, int S)
{
Temp=Heap[P], Heap[P]=Heap[S], Heap[S]=Temp;
}
void Insert ()/*Min Heap*/
{
int S=L, P=L/2;
while(S>=2 && Heap[P].F>Heap[S].F)
Swap(P,S), S=P, P=S/2;
}
void Delete ()
{
int P=1, S=2*P;
Swap(1,L), L--;
while(S<=L)
{
if(S<L && Heap[S+1].F<Heap[S].F) S++;
if(Heap[P].F<=Heap[S].F) break;
Swap(P,S), P=S, S=2*P;
}
}
/*Heap以上*/
void Judge(int Nx, int Ny, int Cx, int Cy)/*near,x,y*/
{
if(Nx<0 || Nx>=N || Ny<0 || Ny>=M) return;
if(Dis[Nx][Ny] > Dis[Cx][Cy]+Map[Nx][Ny])
Dis[Nx][Ny]=Dis[Cx][Cy]+Map[Nx][Ny],
Heap[++L].F=Dis[Nx][Ny], Heap[L].x=Nx, Heap[L].y=Ny,
Insert();
}
void Search(int N, int M)
{
Sx=0, Sy=0, Gx=N-1, Gy=M-1;
int Cx, Cy;
L=1, Heap[1].x=Sx, Heap[1].y=Sy;
Dis[0][0]=Map[0][0];
while( L>0 )
{
Cx=Heap[1].x, Cy=Heap[1].y;
if(Cx==Gx && Cy==Gy) break;
Delete();
Judge (Cx+1,Cy,Cx,Cy);
Judge (Cx-1,Cy,Cx,Cy);
Judge (Cx,Cy+1,Cx,Cy);
Judge (Cx,Cy-1,Cx,Cy);
}
printf("%d\n",Dis[Gx][Gy]);
}
main()
{
while(scanf("%d",&T)==1)
while(T--)
{
scanf("%d %d",&N,&M);
int Sum=0;
for(a=0;a<N;a++)
for(b=0;b<M;b++)
getchar(), Map[a][b]=getchar()-'0', Dis[a][b]=MaxValue, Sum+=Map[a][b];
if(Sum)
Search (N, M);
else puts("0");
}
return 0;
}
/* Problem: d793 "929 - Number Maze" from UVa ACM 929 */
/* Language: C (1909 Bytes) */
/* Result: AC judge by zeroserver@ZeroJudge */
/* Author: morris1028 at 2010-09-22 11:43:39 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MaxValue 32767
#define Size 1000
char Map[Size][Size];
short Dis[Size][Size];
int T, N, M, a, b;
int Sx, Sy, Gx, Gy, L;
struct Heap
{
short x, y, F;
}Heap[1000000], Temp;
/*Heap以下*/
void Swap(int P, int S)
{
Temp=Heap[P], Heap[P]=Heap[S], Heap[S]=Temp;
}
void Insert ()/*Min Heap*/
{
int S=L, P=L/2;
while(S>=2 && Heap[P].F>Heap[S].F)
Swap(P,S), S=P, P=S/2;
}
void Delete ()
{
int P=1, S=2*P;
Swap(1,L), L--;
while(S<=L)
{
if(S<L && Heap[S+1].F<Heap[S].F) S++;
if(Heap[P].F<=Heap[S].F) break;
Swap(P,S), P=S, S=2*P;
}
}
/*Heap以上*/
void Judge(int Nx, int Ny, int Cx, int Cy)/*near,x,y*/
{
if(Nx<0 || Nx>=N || Ny<0 || Ny>=M) return;
if(Dis[Nx][Ny] > Dis[Cx][Cy]+Map[Nx][Ny])
Dis[Nx][Ny]=Dis[Cx][Cy]+Map[Nx][Ny],
Heap[++L].F=Dis[Nx][Ny], Heap[L].x=Nx, Heap[L].y=Ny,
Insert();
}
void Search(int N, int M)
{
Sx=0, Sy=0, Gx=N-1, Gy=M-1;
int Cx, Cy;
L=1, Heap[1].x=Sx, Heap[1].y=Sy;
Dis[0][0]=Map[0][0];
while( L>0 )
{
Cx=Heap[1].x, Cy=Heap[1].y;
if(Cx==Gx && Cy==Gy) break;
Delete();
Judge (Cx+1,Cy,Cx,Cy);
Judge (Cx-1,Cy,Cx,Cy);
Judge (Cx,Cy+1,Cx,Cy);
Judge (Cx,Cy-1,Cx,Cy);
}
printf("%d\n",Dis[Gx][Gy]);
}
main()
{
while(scanf("%d",&T)==1)
while(T--)
{
scanf("%d %d",&N,&M);
int Sum=0;
for(a=0;a<N;a++)
for(b=0;b<M;b++)
getchar(), Map[a][b]=getchar()-'0', Dis[a][b]=MaxValue, Sum+=Map[a][b];
if(Sum)
Search (N, M);
else puts("0");
}
return 0;
}