BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫(BFS)

水题一道却交了4次QAQ，真是蒟蒻QAQ

CODE：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int x,y,t;
}st,en;
queue<node> s;
#define maxn 1010
int a[maxn][maxn];
bool b[maxn][maxn];
int w[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m;
char str[10000];
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
  scanf("%s",str);
  for (int j=1;j<=m;j++){
   if (str[j-1]=='#') a[i][j]=1;
   else if (str[j-1]=='@') {st=(node){i,j,0};a[i][j]=1;}
   else if (str[j-1]=='=') en=(node){i,j,0};
   else if (str[j-1]!='.')a[i][j]=str[j-1];
  }
}
s.push(st);
for (int i=1;i<=n;i++) a[i][0]=a[i][m+1]=1;
for (int i=1;i<=m;i++) a[0][i]=a[n+1][i]=1;
while (!s.empty()){
  node u=s.front();
  if (u.x==en.x&&u.y==en.y) {printf("%d",u.t);return 0;}
  s.pop();
  for (int i=0;i<4;i++)
   if (a[u.x+w[i][0]][u.y+w[i][1]]!=1){
    if (a[u.x+w[i][0]][u.y+w[i][1]]>1){
     if (b[u.x+w[i][0]][u.y+w[i][1]]) continue;
     b[u.x+w[i][0]][u.y+w[i][1]]=1;
     for (int k=1;k<=n;k++)
      for (int j=1;j<=m;j++)
       if ( a[k][j]==a[u.x+w[i][0]][u.y+w[i][1]] &&(u.x+w[i][0]!=k||u.y+w[i][1]!=j) ) {s.push((node){k,j,u.t+1});}
    }else {
    a[u.x+w[i][0]][u.y+w[i][1]]=1;
    s.push((node){u.x+w[i][0],u.y+w[i][1],u.t+1});
    }
    }
}
return 0;
}

巴特西

BZOJ 3299: [USACO2011 Open]Corn Maze玉米迷宫(BFS)

最新文章

热门文章