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.

2
Contributors
1
Reply
2
Views
7 Years
Discussion Span
Last Post by Ancient Dragon
0

You are assuming everyone knows that SHOP, BFS, and TLE mean. We don't. You might get more help if you would provide links to that.

Also, that appears to be a C program, not C++.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.