一道 flood fill.
如果你WA了, 那么请注意: 这个迷宫可能不通, 要两头搜.
#include<iostream> using namespace std; int n; char s[35][40]; int A[37][37]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int went[37][37]; int tot; void floodfill(int x,int y) { int i; if(went[x][y]) return; went[x][y]=1; for(i=0;i<4;i++) { if(went[x+dir[i][0]][y+dir[i][1]]) continue; if(!A[x+dir[i][0]][y+dir[i][1]]) tot++; else floodfill(x+dir[i][0],y+dir[i][1]); } return; } int main() { int i,j,k; scanf("%d",&n); for(i=0;i<n;i++) scanf("%s",s[i]); for(i=0;i<n;i++) for(j=0;j<n;j++) if(s[i][j]=='.') A[i+1][j+1]=1; floodfill(1,1); floodfill(n,n); printf("%d/n",(tot-4)*9); return 0; }
给点测试数据(Discuss上的)
3...###...
Answer is 1085..#....#..#####..#....#..Answer is 108
And there's a BIG TEST33............#........#....##.........#..##.........#.....##..#.........#.##....#...........#.#####.#..###.....#..............#.....#......##......#.##..#.....#.....####.##.#.........##.#.....#.#.#....#..#.##......#.###.#.....#.###.##.......##....#.#..##.##.#.#........##.....#.............#..#....#...###.###......#..#..#.....###.##......##..#..#....#......###....#...#.#..#######..#..####...........##.#.........##....##...............#...#......#....###....#.#....#.#.........#.#..##......#...#..##..#...#.#..#.#####..##....#.#.....#......#.#..##.#...#.###.............#...#..##....##...#...#..##.#..#...#..#..##............#...........#..#.#.#....#.....##..#.#.#...####..#...#..#....#.#.....#.....#.#.......##.#.#.#...##.#...#..##....#.................#..#.......#..#.###......#.....#......#.......#.....#.....#...............#.####......#....###..........#.#.##.#.....##..##........#.##...#......#.#.##....#......#.#....#..........##....#.#..#####.#.........#..#.#.....###.....#...#....#..........#..#.#...##........#.........#....#..#.........#............#..#.......##.##..#.........
ANSWER 7812
