直接中文
样例1
样例2
3 6 5 NEESWE WWWESS SNWWWW 4 5 1 SESWE EESNW NWEEN EWSEN 0 0 0
10 step(s) to exit 3 step(s) before a loop of 8 step(s)
https://vjudge.net/problem/POJ-1573
没啥说的,直接dfs搜就行
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 25 using namespace std; int r,c,s;//行,列,从第s列开始 char mp[Maxn][Maxn];//地图 int vis[Maxn][Maxn];//标记是否走过 int step[Maxn][Maxn];//(x,y)是第几步 //(x,y) 下一步的字母标志 到(x,y)已是第step步 void dfs(int x,int y,char op,int start) { //走出迷宫 if(mp[x][y]==‘X‘||x<1&&y<1&&x>r&&y>c) cout<<start<<" step(s) to exit"<<endl; //(x,y)没走过 else if(!vis[x][y]) { vis[x][y]=1; step[x][y]=start+1; //四种走法 if(op==‘N‘) return dfs(x-1,y,mp[x-1][y],step[x][y]); if(op==‘S‘) return dfs(x+1,y,mp[x+1][y],step[x][y]); if(op==‘E‘) return dfs(x,y+1,mp[x][y+1],step[x][y]); if(op==‘W‘) return dfs(x,y-1,mp[x][y-1],step[x][y]); } //(x,y)走过,输出即可 else if(vis) cout<<step[x][y]-1<<" step(s) before a loop of "<<start+1-step[x][y]<<" step(s)"<<endl; } int main() { while(cin>>r>>c>>s,r+c+s) { //初始化 MEM(mp,‘X‘); MEM(vis,0); MEM(step,0); for(int i=1; i<=r; i++) for(int j=1; j<=c; j++) cin>>mp[i][j]; step[1][s]=0; dfs(1,s,mp[1][s],step[1][s]); } }
原文:https://www.cnblogs.com/sky-stars/p/11204430.html