问题标题: 酷町堂：1099 蚂蚁（30分）

通往本题的黑洞

我竟然神奇地获得了30分！！！

不过还不是AC。。。

望各位大佬看看我的程序哪里错了，走过路过不要错过！

问题代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],cx,cy,ex,ey,b[1001][1001],sum=10007;
int m,n;
struct node{
	int x,y,hp,bs;
}tmp,h;
int dir[5][2]={{0},{0,1},{0,-1},{-1,0},{1,0}};
queue<node> q;
void bfs()
{
	tmp.hp=6,tmp.x=cx,tmp.y=cy,tmp.bs=0;
	b[cx][cy]=1;
	q.push(tmp);
	while(!q.empty()){
		h=q.front();
		q.pop();
		if(h.x==ex&&h.y==ey&&h.hp>0){
			sum=min(sum,h.bs);
		}
		for(int i=1;i<=4;i++){
			int nx=h.x+dir[i][0],ny=h.y+dir[i][1];
			if(nx>=1&&nx<=m&&ny<=n&&ny>=1&&!b[nx][ny]){
				tmp.x=nx,tmp.y=ny,tmp.hp=h.hp-1,tmp.bs=h.bs+1;
				q.push(tmp);
				b[nx][ny]=1;
			}
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	for(int j=1;j<=n;j++){
    		cin>>a[i][j];
    		if(a[i][j]==2) cx=i,cy=j;
    		if(a[i][j]==3) ex=i,ey=j;
		}
	}
	bfs();
	if(sum==10007) cout<<-1;
	else cout<<sum;
    return 0;
} 

广度优先搜索代码。

陶旭杰在2019-10-26 12:23:41追加了内容

修改了一下下，变成了90分。。。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001],cx,cy,ex,ey,b[1001][1001],sum=10007;
int m,n;
struct node{
	int x,y,hp,bs;
}tmp,h;
int dir[5][2]={{0},{0,1},{0,-1},{-1,0},{1,0}};
queue<node> q;
void bfs()
{
	tmp.hp=6,tmp.x=cx,tmp.y=cy,tmp.bs=0;
	b[cx][cy]=1;
	q.push(tmp);
	while(!q.empty()){
		h=q.front();
		q.pop();
		if(h.x==ex&&h.y==ey&&h.hp>0){
			sum=min(sum,h.bs);
		}
		if(h.hp==0) continue;
		if(a[h.x][h.y]==4) h.hp=6;
		for(int i=1;i<=4;i++){
			int nx=h.x+dir[i][0],ny=h.y+dir[i][1];
			if(nx>=1&&nx<=m&&ny<=n&&ny>=1&&!b[nx][ny]&&a[nx][ny]){
				tmp.x=nx,tmp.y=ny,tmp.hp=h.hp-1,tmp.bs=h.bs+1;
				q.push(tmp);
				b[nx][ny]=1;
			}
		}
	}
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	for(int j=1;j<=n;j++){
    		cin>>a[i][j];
    		if(a[i][j]==2) cx=i,cy=j;
    		if(a[i][j]==3) ex=i,ey=j;
		}
	}
	bfs();
	if(sum==10007) cout<<-1;
	else cout<<sum;
    return 0;
}