问题标题: 酷町堂：2147

Question

0

已解决

康曦

中级光能

问一下2147我这个dfs哪里错了

题目出门左转

我的20分WA代码

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int k,dir[201][21]={{0},{-1,0},{0,1},{1,0},{0,-1}},x,y,a,b,n;
bool vis[101][101],f[101][101];
string l="NO";
void kx(int ex,int ey){
    f[ex][ey]=true;
    if(ex==a&&ey==b){
        l="YES";
        return ;
    }
    for(int i=1;i<=4;i++){
        int dx=ex+dir[i][0],dy=ey+dir[i][1];
        if(!vis[dx][dy]&&!f[dx][dy]&&dx>=1&&dy>=1&&dx<=n&&dy<=n){
            kx(dx,dy);
        }
    }
    return ;
}
int main(){ 
    ///freopen("3849.in","r",stdin);
    //freopen("3849.out","w",stdout);
    cin>>k;
    while(k--){
        l="NO";
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char g;
                cin>>g;
                if(g=='d') vis[i][j]=true; 
                else vis[i][j]=false;
                f[i][j]=false; 
            }
        }
        cin>>x>>y>>a>>b;
        kx(x,y);
        cout<<l<<endl;
    }
    //fclose(stdout);
    return 0;
}

Answer 1

已采纳

吴庞茂旭

资深光能

对方向你投去了70分代码。

头文件
方向数组
一大堆定义
void dfs(int x,int y){
    book[x][y]=true;
    if(x==ex&&y==ey){
        flag=true;
        return;
    }
    if(flag)return;
    for(int i=1;i<=4;i++){
        int dx=x+dir[i][0],dy=y+dir[i][1];
        if(dx>=1&&dy>=1&&dx<=n&&dy<=n&&a[dx][dy]=='s'&&!book[dx][dy]){
            dfs(dx,dy);
            book[dx][dy]=false;
        }
    }
    return;
}
int main(){
    输入
    循环t次
        一大波输入
        标志杆置位false;
        if(起始点或终点是'd'){
            cout<<"NO\n";
        } else{
            dfs(起始x，起始y);
            printf("%s\n",根据题目输出);
        }
    }
    return 0;
}

貌似我多了一步操作，你仔细品吧。

问题标题: 酷町堂：2147

1 个回答: