Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴代码。给个小思路，遇到这种迷宫的题最好扩展边界，1A。

Posted by frankLEE at 2015-05-15 20:20:21 on Problem 1573
```#include <iostream>
#include <string>
using namespace std;

const int N = 14;
char grid[N][N];
int length[N][N];
bool visit[N][N];

void dfs(int x, int y, int &path, int &loop);

int main()
{
int  height = 0, width = 0;
while (1)
{
int start = 0;
cin >> height >> width >> start;
if (height + width + start == 0)  break;

memset(length, 0, sizeof(length));
memset(visit, false, sizeof(visit));
int path = 0, loop = 0;

for (int i=1; i<=height; i++)
{
for (int j=1; j<=width; j++)  cin >> grid[i][j];
}

for (int i=0; i<=width+1; i++)
{
grid[0][i] = 'A';
grid[height+1][i] = 'A';
}

for (int i=0; i<=height+1; i++)
{
grid[i][0] = 'A';
grid[i][width+1] = 'A';
}

dfs(1, start, path, loop);

if (loop == 0)  cout << path << " step(s) to exit" << endl;
else cout << path << " step(s) before a loop of " << loop << " step(s)" << endl;

}
return 0;
}

void dfs(int x, int y, int &path, int &loop)
{
if (loop > 0)  return;
if (grid[x][y] == 'A')
{
path = length[x][y];
return ;
}

visit[x][y] = true;
if(grid[x][y] == 'W')
{
if (visit[x][y-1] == false)
{
length[x][y-1] = length[x][y] + 1;
dfs(x, y-1, path, loop);
}
else
{
loop = length[x][y] - length[x][y-1] + 1;
path = length[x][y-1];
}
}

if(grid[x][y] == 'S')
{
if (visit[x+1][y] == false)
{
length[x+1][y] = length[x][y] + 1;
dfs(x+1, y, path, loop);
}
else
{
loop = length[x][y] - length[x+1][y] + 1;
path = length[x+1][y];
}
}

if(grid[x][y] == 'E')
{
if (visit[x][y+1] == false)
{
length[x][y+1] = length[x][y] + 1;
dfs(x, y+1, path, loop);
}
else
{
loop = length[x][y] - length[x][y+1] + 1;
path = length[x][y+1];
}
}

if(grid[x][y] == 'N')
{
if (visit[x-1][y] == false)
{
length[x-1][y] = length[x][y] + 1;
dfs(x-1, y, path, loop);
}
else
{
loop = length[x][y] - length[x-1][y] + 1;
path = length[x-1][y];
}
}
}```

Followed by: