求大佬救救蒟蒻,就一个点过不了
查看原帖
求大佬救救蒟蒻,就一个点过不了
218974
wsadjkl0楼主2021/6/15 14:19
#include<bits/stdc++.h>
using namespace std;
void print(void);
int xx[200], yy[200];//记录搜索路径
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, 0, -1, 1};

int n, m, cnt, p;
char mark[105][105];
char s[105][105], c;

//检查搜索路径周围是否有漏掉的联通点,漏掉输出0
int check(void){
    int x, y;
    for(int j = 0; j < p; j++){
    x = xx[j], y =yy[j];
	for(int i = 0; i < 8; i++){
        int curx = x+dx[i], cury = y+dy[i];
        if(curx < 0 || cury < 0 || curx >= n || cury >= m) continue;
		if(mark[x+dx[i]][y+dy[i]] == 0) return 0;
    }
    }
	return 1;
}

//每次搜索都记录路径,先压点然后继续搜
void dfs(int x, int y){
    xx[p] = x; yy[p] = y; p++;
	mark[x][y] = 1;
	if(check()) { cnt++; }
	for(int i = 0; i < 9; i++){
		int curx = x+dx[i], cury = y+dy[i];
		if(curx < 0 || cury < 0 || curx >= n || cury >= m) continue;//判断合法
		if(mark[curx][cury] == 0) dfs(curx, cury);
	}
    p--;
}


int main(){
	cin >> n >> m;
	memset(mark, -1, sizeof(mark));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
            cin >> s[i][j];
			if(s[i][j] == 'W') mark[i][j] = 0;
		}
	}
   //填水坑
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(mark[i][j] == 0) dfs(i, j);
		}
	}
	cout << cnt;
	return 0;
}

void print(void){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
            printf("%3d", mark[i][j]);
		}
        putchar('\n');
	}
}
2021/6/15 14:19
加载中...