用的BFS,过了样例为啥全错?

#include <iostream>
using namespace std;
struct node
{
int x;
int y;
};
char map[700][700];
int book[700][700] = { 0 };
node que[250001];
int direction[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int is_Safe(int x, int y)
{

int k;
int tx, ty;
int sum = 0;
for (k = 0; k<4; k++)
{
tx = x + direction[k][0];
ty = y + direction[k][1];
if (map[tx][ty] == '*')
sum++;
}
if (sum == 4)
return 1;
else
return 0;
}
int main()
{
int x, y, i, j, k, sum = 0;
cin >> x >> y;
for (i = 1; i <= x; i++)
for (j = 1; j <= y; j++)
cin >> map[i][j];
int head, tail;
head = 1;
tail = 1;
que[tail].x = 1;
que[tail].y = 1;
tail++;

int flag = 0, tx = 1, ty = 1;
if (map[tx][ty] == '0'&&book[tx][ty] == 0 && is_Safe(tx, ty))
sum++;
book[1][1] = 1;
while (head<tail)
{
for (k = 0; k<4; k++)
{
tx = que[head].x + direction[k][0];
ty = que[head].y + direction[k][1];
if (tx<1 || tx>x || ty<1 || ty>y)
continue;
if (map[tx][ty] == '0'&&book[tx][ty] == 0 && is_Safe(tx, ty))
sum++;
if (book[tx][ty] == 0)
{
book[tx][ty] = 1;
que[tail].x = tx;
que[tail].y = ty;
tail++;
}
if (tx>x&&ty>y)
{
flag = 1;
break;
}
}
if (flag == 1)
break;
head++;
}
cout << sum << endl;
return 0;
}

0 条评论

目前还没有评论...

信息

ID
1294
难度
6
分类
搜索 点击显示
标签
(无)
递交数
1839
已通过
555
通过率
30%
被复制
3
上传者