MLASERP - Laser Phones
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
int cols,rows;
char map[128][128];
int cowrow1,cowcol1,cowrow2,cowcol2;
void read_input()
{
int row,col,cows = 0;
scanf("%d %d",&cols,&rows);
for(row = 0;row<rows;row++)
{
scanf("%s",map[row]);
for(col = 0;col<cols;col++) if(map[row][col] =='C')
{
if(cows==0) {cowrow1 = row;cowcol1 = col;}
if(cows==1){ cowrow2 = row; cowcol2 = col;}
cows++;
}
}
}
int calc_steps()
{
int DR[] = {-1,0,0,1};
int DC[] = {0,-1,1,0};
int steps[128][128];
int queue[128*128];
int readptr,writeptr;
int r,c,d,rr,cc;
map[cowrow2][cowcol2]='.';
map[cowrow1][cowcol1]='+';
steps[cowrow1][cowcol1] = 1;
queue[0] = 128*cowrow1+cowcol1;
readptr = 0;
writeptr = 1;
while(steps[cowrow2][cowcol2] ==0)
{
r = queue[readptr]/128;
c = queue[readptr++]%128;
for(d=0;d<4;d++)
{
rr = r;
cc = c;
while(true)
{
rr+=DR[d];cc+=DC[d];
if((rr<0)||(rr>rows)||(cc<0)||(cc>cols)||map[rr][cc]=='*') break;
if(map[rr][cc]!='.') continue;
map[rr][cc]='+';
steps[rr][cc] = steps[r][c] +1;
queue[writeptr++] = 128*rr+cc;
}
}
}
return steps[cowrow2][cowcol2] - 2;
}
int main()
{
//freopen("MLASERP2.inp","r",stdin);
read_input();
printf("%d\n",calc_steps());
//getch();
}