这道题很坑的地方很多。。
首先cin>>m>>n;那个坐标我就没整对，
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cin>>m[i][j];
}
然后手动写了些才发现问题。
还有map，和visit，我之前吧visit遗漏了，只记得标志了，
还有入口和出口也是可走的，之前忘了标志。
还有俩深搜，一广搜，我之前都想成广搜了，
还有审题。。。。S的位置只在边缘，这样才好判断方向。。。
以下的代码要着重注意深搜里的方向。。很重要。。。本题难点吧。。。
Children of the Candy Corn
Input Input to this problem will begin with a line containing a single integer n indicating the number of mazes. Each maze will consist of one line with a width, w, and height, h (3 <= w, h <= 40), followed by h lines of w characters each that represent the maze layout. Walls are represented by hash marks ('#'), empty space by periods ('.'), the start by an 'S' and the exit by an 'E'. < br>< br>Exactly one 'S' and one 'E' will be present in the maze, and they will always be located along one of the maze edges and never in a corner. The maze will be fully enclosed by walls ('#'), with the only openings being the 'S' and 'E'. The 'S' and 'E' will also be separated by at least one wall ('#'). < br>< br>You may assume that the maze exit is always reachable from the start point.
Output For each maze in the input, output on a single line the number of (not necessarily unique) squares that a person would visit (including the 'S' and 'E') for (in order) the left, right, and shortest paths, separated by a single space each. Movement from one square to another is only allowed in the horizontal or vertical direction; movement along the diagonals is not allowed.
Sample Input 2 8 8 ######## #......# #.####.# #.####.# #.####.# #.####.# #...#..# #S#E#### 9 5 ######### #.#.#.#.# S.......E #.#.#.#.# #########
Sample Output 37 5 5 17 17 9
以下是我的代码：
#include<iostream> #include<queue> #include<string.h> using namespace std; int map[100][100]={0}; int visit[100][100]={0}; int dir[4][2]={ {0,1}, {1,0}, {0,-1},{-1,0}};
int m,n; int flag=0;
int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; struct y { int begin; int end; int step; }; y e1,e2; queue<y>mm; int bfs(int si,int sj,int ei,int ej ) {
int shuchu; //int jishu=0; y y1,y2;
y1.begin=si; y1.end=sj; y1.step=1; mm.push(y1); visit[y1.begin][y1.end]=1; while(mm.empty()==0) { //jishu++; y1=mm.front(); mm.pop(); if(y1.begin==ei&&y1.end==ej) { shuchu=y1.step; }
for(int i=0;i<4;i++) { y2.begin=y1.begin+dx[i]; y2.end=y1.end+dy[i]; y2.step=y1.step+1; if(y2.begin>=0&&y2.begin<n&&y2.end>=0&&y2.end<m&&map[y2.begin][y2.end]==1&&visit[y2.begin][y2.end]==0) { mm.push(y2); visit[y2.begin][y2.end]=1; } } } return shuchu; }
int dfs(int si,int sj,int fang,int xpp) { int xin; if(si==e2.begin&&sj==e2.end) return 1; if(xpp==1)//left { for(int i = fang-1; i <= fang+2; i++) { xin = (i+4)%4; int x = si + dir[xin][0]; int y = sj + dir[xin][1]; if(x >= 0 && x < n && y>= 0 && y < m && map[x][y] ==1) { return dfs(x,y,xin,xpp) + 1; } } } else if(xpp==2) { for(int i = fang+1; i >= fang-2; i--) { xin = (i+4)%4; int x= si + dir[xin][0]; int y= sj + dir[xin][1]; if(x >= 0 && x< n && y >= 0 && y < m && map[x][y] ==1) { return dfs(x,y,xin,xpp) + 1; } }
} }
int main() { //y e1,e2; int t; char s; cin>>t; while(t--) { cin>>m>>n; memset(map,0,sizeof(map)); memset(visit,0,sizeof(visit)); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>s; if(s=='.'||s=='S'||s=='E') map[i][j]=1; if(s=='S') { e1.begin=i; e1.end=j; } if(s=='E') { e2.begin=i; e2.end=j; } } }
int fang; if(e1.begin== 0) fang = 1; else if(e1.begin== n-1) fang = 3; else if(e1.end== 0) fang= 0; else if(e1.end== m-1) fang= 2; cout<<dfs(e1.begin,e1.end,fang,1)<<" "; cout<<dfs(e1.begin,e1.end,fang,2)<<" "; cout<<bfs(e1.begin,e1.end,e2.begin,e2.end)<<endl;
} }
