在刷题时刷到P1825题,看起来挺简单的,于是开写:
我用BFS写这题,一个低级错误 (我才不告诉你是vis忘记开了) ,样例居然还过了。
#include <bits/stdc++.h>
using namespace std;
int n,m,startx,starty,endx,endy,out[2];
char map_[305][305];
int chuansong[135][2];
const int dx[4] = {0,0,-1,1},dy[4] = {-1,1,0,0};
void to(int x,int y)
{
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(i != x && j != y && map_[i][j] == map_[x][y])
{
out[0] = i;
out[1] = j;
}
}
}
}
struct node
{
int x,y,steps;
};
queue<node>q;
int main(void)
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> map_[i][j];
if(map_[i][j] == '@')
{
startx = i;
starty = j;
}else if(map_[i][j] == '=')
{
endx = i;
endy = j;
}
}
}
q.push((node){startx,starty,0});
while(q.size())
{
node tmp;
tmp = q.front();
q.pop();
if(tmp.x == endx && tmp.y == endy)
{
cout << tmp.steps;
return 0;
}
for(int i = 0;i < 4;i++)
{
int nx = tmp.x+dx[i],ny = tmp.y+dy[i];
if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
if(map_[nx][ny] == '#') continue;
if(map_[nx][ny] >= 'A' && map_[nx][ny] <= 'Z')
{
to(nx,ny);
nx = out[0];
ny = out[1];
}
q.push((node){nx,ny,tmp.steps+1});
}
}
return 0;
}
这个故事告诉我们,不能依赖题目的样例!!!
小小的说一句,这题的数据是真的水,这样的错误居然拿了13分