- #include < cstdio > #include < cstring > #include < cstdlib > #include < iostream > #include < algorithm > #define N 100 using namespace std;
- char ch;
- bool vis[N][N];
- int a[N][N],
- cnt,
- tot,
- sx,
- sy,
- ans;
- int xx[4] = {
- 0,
- 0,
- 1,
- -1
- },
- yy[4] = {
- 1,
- -1,
- 0,
- 0
- };
- int pd(int x, int y) {
- tot++;
- vis[x][y] = true;
- for (int i = 0; i < 4; i++) {
- int fx = x + xx[i],
- fy = y + yy[i];
- if (!vis[fx][fy] && fx > 0 && fy > 0 && fx <= 5 && fy <= 5 && a[fx][fy]) pd(fx, fy);
- }
- }
- int dfs(int x, int y, int now) {
- if (!now) {
- tot = 0;
- memset(vis, 0, sizeof(vis));
- pd(sx, sy);
- return (cnt + ans) == tot;
- }
- for (int fy = y + 1; fy <= 5; fy++) {
- if (a[x][fy]) continue;
- a[x][fy] = true;
- if (dfs(x, fy, now - 1)) return 1;
- a[x][fy] = false;
- }
- for (int fx = x + 1; fx <= 5; fx++) for (int fy = 1; fy <= 5; fy++) {
- if (a[fx][fy]) continue;
- a[fx][fy] = true;
- if (dfs(fx, fy, now - 1)) return 1;
- a[fx][fy] = false;
- }
- return 0;
- }
- int main() {
- for (int i = 1; i <= 5; i++) {
- for (int j = 1; j <= 5; j++) {
- scanf("%c", &ch);
- a[i][j] = ch - ‘0‘;
- if (a[i][j]) sx = i,
- sy = j,
- cnt++;
- }
- if (i != 5) scanf("\n");
- }
- for (ans = 1;; ans++) {
- if (dfs(1, 1, ans)) {
- printf("%d", ans);
- return 0;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2317162.html