Question

为什么这个代码会超过1000MS呢？急求。谢谢！ 题目：http://poj.grids.cn/practice/372

#include"stdio.h"
#include"iostream"
using namespace std;

int i,j,m,n;
int ax,ay,bx,by;
char t,path[21][21];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int queue[400][3];
int left1,right1;

int inarea(int x,int y) {
return(x>=0&&x<n&&y>=0&&y<m);
}

int bfs() {
int tx,ty;
left1=right1=0;
queue[0][0]=ax;
queue[0][1]=ay;
queue[0][2]=0;
path[ay][ax]='#';
right1++;

while(left1<right1) {
if(queue[left1][0]==bx&&queue[left1][1]==by)
return queue[left1][2];
for(int k=0;k<4;++k) {
tx=queue[left1][0]+dx[k];
ty=queue[left1][1]+dy[k];
if(inarea(tx,ty)&&path[ty][tx]!='#') {
queue[right1][0]=tx;
queue[right1][1]=ty;
queue[right1++][2]=queue[left1][2]+1;
path[ty][tx]='#';
}
}
++left1;
}
return -1;
}
int main() {
while(scanf("%d%d",&m,&n),m!=0&&n!=0) {
getchar();
for(i=0;i<m;i++) {
for(j=0;j<n;j++) {
t=getchar();
if(t=='@') {
ax=j;
ay=i;
}
if(t=='*') {
bx=j;
by=i;
}
path[i][j]=t;
}
getchar();
}
printf("%d\n",bfs());
}
}

Answer 1

你的解法与http://hi.baidu.com/yjy2410578/blog/item/dafc1bfa6cb359d6b58f31b2.html相似。但后者在处理输入时还判断是否有'*'，如果没有就立即输出-1。

Answer 2

for循环太多了，这会浪费掉很多时间

追问

可是FOR循环是按嵌套层数来算时间的啊。而且广搜做标记了。会快啊