题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

include[HTML_REMOVED]

using namespace std;

const int N=101;
char g[N][N];
int st[N][N];

int n,m;
int xa,ya,xb,yb;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

bool dfs(int x,int y){
if(x==xb&&y==yb){
return true;
}

st[x][y]=1;

int a,b;
for(int i=0;i<4;i++){
    a=x+dx[i],b=y+dy[i];
    if(a<0||a>m-1||b<0||b>m-1) continue;
    if(g[a][b]=='#'||st[a][b]) continue;
    if(dfs(a,b)) return true;
}

return false;

}

int main(){
cin>>n;
while(n–){
memset(st,0,sizeof st);
cin>>m;
for(int i=0;i[HTML_REMOVED]>g[i];
}

    cin>>xa>>ya>>xb>>yb;
    if(g[xa][ya]=='#'||g[xb][yb]=='#'){
        puts("NO");
        continue;
    }
    if(dfs(xa,ya)) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}

}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla