0

Hi all,

My code for SHOP is as follows, problem description here.

```
#include<iostream>
#include<queue>
#include<climits>
using namespace std;
class pt{
public:
int _x,_y,_cost;
pt(){}
pt(int x,int y,int z):_x(x),_y(y),_cost(z){}
int print(){
printf("%d %d %d\n",_x,_y,_cost);
}
};
int dx[]={0,-1,0,1};
int dy[]={-1,0,1,0};
int main( ) {
int M,N;
while(scanf("%d %d",&N,&M)!=EOF){
if(!M&&!N)break;
bool flag=false;
char sq[25][26];
bool visit[25][25];
memset(visit,false,sizeof(visit));
queue<pt> q;
for(int i=0;i<M;++i){
scanf("%s",sq[i]);
if(!flag)
for(int j=0;j<strlen(sq[i]);++j)if(sq[i][j]=='S'){flag=true;q.push(pt(i,j,0));break;}
}
int min=100000000;
while(q.size()>0){
pt cur=q.front();
q.pop();
int x=cur._x,y=cur._y,cost=cur._cost;
visit[x][y]=true;
if(sq[x][y]=='D'){
min<?=cost;
continue;
}
for(int i=0;i<4;++i){
int nx=dx[i]+x,ny=dy[i]+y;
if(nx<0||nx>=M||ny<0||ny>=N)
continue;
if(visit[nx][ny]==false&&sq[nx][ny]!='X'){
int tmp=sq[nx][ny]=='D'?0:sq[nx][ny]-'0';
q.push(pt(nx,ny,cost+tmp));
}
}
}
printf("%d\n",min);
}
return 0;
}
```

My idea is BFS, but getting TLE. Any other ideas?

Thanks in Advance.