寻找国都名
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1427
题目描述
给出一个字符矩阵及要寻找的国都名，要求从这个矩阵中找到这个国都名，并输出这个国都名的起始位置及搜索的方向。搜索可沿8个方向进行，见下图：
输入
第一行有一个整数M和N（1<=M，N<=10），表示该字符矩阵的长和宽。接下来就是M*N的字符矩阵。接下来一行是一串字符，代表要寻找的国都名。
输出
如果没有找到，则输出“No Answer!”；
如果有找到，输出分两行，第一行为国都名的起始位置坐标，第二行为寻找的方向
样例输入
8 8 okdublin alpgocev rasmusmb oslondon yibdglrc krzurich oaibxmuz tpqglamv dublin
样例输出
1 3 11111
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<string> #include<cstring> using namespace std; char mp[11][11]; string a; bool ans=0; int l,x[8]={1,-1,0,0,-1,1,1,-1},y[8]={0,0,1,-1,1,-1,1,-1}; int b[11]; int m,n; bool pd(int k,int i,int j) { if(mp[i][j]!=a[k]||i<=0||j<=0||i>m||j>n)return 0; return 1; } void dfs(int k,int i,int j) { if(!pd(k,i,j))return; if(k==l-1)ans=1; for(int s=0;s<8;s++) { if(ans)return; b[k]=s+1; dfs(k+1,i+y[s],j+x[s]); } } int main() { cin>>m>>n; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>mp[i][j]; cin>>a; l=a.length(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { dfs(0,i,j); if(ans) { cout<<i<<' '<<j<<endl; int k=0; while(b[k]!=0)cout<<b[k++]; return 0; } } cout<<"No Answer!"; return 0; } |
Subscribe
计数器 9320763
OI 课件=>
OI 课件=>