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

## dfs水过

Posted by Ink213 at 2013-04-04 18:58:57 on Problem 1573
```#include<cstdio>
#include<cstring>
using namespace std;
int n, m, s;
int dx[6]={0,0,-1,1};
int dy[6]={1,-1,0,0};
int map[20][20], nd[20][20], fd, a, b;
bool flag, vis[20][20];
void dfs(int x,int y,int dist)
{
int nx, ny;
nd[x][y]= ++dist;
nx=x+dx[map[x][y]];
ny=y+dy[map[x][y]];
if(nx<1||ny<1||nx>n||ny>m) {fd=dist;return ;}
if(!vis[nx][ny]) {vis[x][y]=true;dfs(nx,ny,dist);}
else {flag=false;a=nd[nx][ny]-1,b=nd[x][y]-nd[nx][ny]+1;return ;}
}
int main()
{
int i, j;
char tmp;
while(scanf("%d%d%d",&n,&m,&s)&&(n||m||s))
{
memset(nd,0,sizeof(nd));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf(" %c",&tmp);
if(tmp=='N') map[i][j]=2;
if(tmp=='S') map[i][j]=3;
if(tmp=='E') map[i][j]=0;
if(tmp=='W') map[i][j]=1;
}
flag=true;
dfs(1,s,0);
if(flag) printf("%d step(s) to exit\n",fd);
else printf("%d step(s) before a loop of %d step(s)\n",a,b);
}
return 0;
}
```

Followed by: