有些地方没想明白
  • 板块P1141 01迷宫
  • 楼主6lszxz
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/1/21 22:50
  • 上次更新2023/10/28 11:36:58
查看原帖
有些地方没想明白
585201
6lszxz楼主2022/1/21 22:50

就是临界条件不会找,然后也不知道在哪里更新答案,如果在递归之前更新的话那么递归之后就要撤销,这样所有的答案就都被撤销了,也没想到别的好办法呜呜QAQ

#include "iostream"
#include "cstring"

using namespace std;

int n,m;

bool puzzle[1010][1010];
//用来存地图的,true代表1,false代表0
bool block[1010][1010];
//用来存走过的格,true代表走过了,false代表没走过。
int used[1010][1010];
//用来打表,存之前走过的地方的可能性次数
int directer[4][2] = {
        {-1,0},//up
        {1,0},//down
        {0,-1},//left
        {0,1}//right
};
int answer=1;


void Search (int x ,int y){

    if(临界){
        used[x][y]=answer;
        memset(block, false,sizeof (block));
        return;
    }
    for(int i=1;i<4;i++){
        int nx = x+directer[i][0];
        int ny = y+directer[i][1];
        if(block[nx][ny]){
            continue;
        }
        if(nx>n || ny>n){
            continue;
        }
        if(nx<1 || ny<1){
            continue;
        }
        if(puzzle[nx][ny]==puzzle[x][y]){
            continue;
        }
        if(used[nx][ny]!=-1){
            answer+=used[nx][ny];
        }
        block[nx][ny] = true;
        answer++;
        Search(nx,ny);
        block[nx][ny] = false;
        answer--;
    }
}

int main(){
    memset(used,-1,sizeof (used));
    memset(block, false,sizeof (block));
    scanf("%d%d",&n,&m);
    int p=1,q=1;
    char c;
    c = getchar();
    for(int i=1;i<=n*n;i++){
        c=getchar();
        if(c=='\r'|| c=='\n'){
            i--;
            q=1;
            p++;
            continue;
        }
        else if(c=='0'){
            puzzle[p][q]= false;
        }
        else if(c=='1'){
            puzzle[p][q]=true;
        }
        q++;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Search(x,y);
        printf("%d\n",answer);
        answer=1;
    }
    return 0;
}
2022/1/21 22:50
加载中...