用洛谷在线ide测试输出明明是一样的,但是一个点都过不了啊
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#define MAX 1501
using namespace std;
struct node
{
int x,y;
};
char ch[MAX][MAX];
int n, m, sx,sy, tag[2*MAX][2*MAX];
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; // 上右下左四个移动方向
queue<node> q;
int mod(int x, int y)
{
return x-int(floor((double(x)/y)))*y; // 自定义取模运算!
}
bool judge(int x, int y)
{
return (x+n == sx && y == sy) || (x+n == sx && y-m == sy) || (x+n == sx && y+m == sy) ||
(x == sx && y+m == sy) || (x == sx && y-m == sy) ||
(x-n == sx && y-m == sy) || (x-n == sx && y == sy) || (x-n == sx && y+m == sy);
}
bool bfs()
{
q.push((node){sx,sy});
tag[sx+MAX][sy+MAX]=1; // 标记时加上MAX
node tmp;
int nx, ny;
while( !q.empty() ){
tmp = q.front(); q.pop();
if( judge(tmp.x, tmp.y) )
return true;
for(int i=0;i<4;i++){
nx=tmp.x+d[i][0]; ny=tmp.y+d[i][1]; // 计算新坐标
if( tag[nx+MAX][ny+MAX] || ch[mod(nx,n)][mod(ny,m)]=='#') continue;
tag[nx+MAX][ny+MAX] = 1; // 标记
q.push((node){nx, ny});
}
}
return false; // 认为没有走出去
}
int main(void)
{
int i, j;
while( scanf("%d %d", &n, &m) ){ // 已知输入直到EOF
getchar(); // 读入回车
// 1. 输入
for(i=0;i<n;i++, getchar()){
for(j=0;j<m;j++){
scanf("%c", ch[i]+j);
if(ch[i][j]=='S'){
sx=i;
sy=j; // 记录起点坐标
}
}
}
// 2. 从起点开始bfs
if(bfs()) printf("Yes\n");
else printf("No\n");
memset(tag, 0, sizeof(tag)); // 更新tag
while( !q.empty() ) q.pop(); //
}
return 0;
}