社区讨论

dfs WA求条

P1002[NOIP 2002 普及组] 过河卒参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mhjawlxv
此快照首次捕获于
2025/11/03 23:34
4 个月前
此快照最后确认于
2025/11/03 23:34
4 个月前
查看原帖
先声明,本人练习DFS,DFS有可能会超时,请指出错误而非提供更好的思路
马蜂丑别介意
CPP
#include<iostream>
using namespace std;
int cnt=0,n,m,mx,my;
int cx[8],cy[8];
void dfs(int x,int y){
    if(x==n&&y==m){
        cnt++;
        return;
    }
    if(x>n||y>m)return;
    int r=1;
    int s=1;
    for(int i=0;i<8;i++){
        if(x+1==cx[i]&&y==cy[i])r=0;
        if(x==cx[i]&&y+1==cy[i])s=0;
    }
    if(s)dfs(x,y+1);
    if(r)dfs(x+1,y);
    else return;
}
int main(){
    cin>>n>>m>>mx>>my;
    cx[0]=mx+1;
    cy[0]=my+2;
    cx[1]=mx+2;
    cy[1]=my+1;
    cx[2]=mx+2;
    cy[2]=my-1;
    cx[3]=mx-2;
    cy[3]=my+1;
    cx[4]=mx+1;
    cy[4]=my-2;
    cx[5]=mx-1;
    cy[5]=my+2;
    cx[6]=mx-2;
    cy[6]=my-1;
    cx[7]=mx-1;
    cy[7]=my-2;
    dfs(1,1);
    cout<<cnt;
    return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...