题目链接:http://www.codechef.com/INSCRP13/problems/INSCTS4
明天早上还有课,所以先刷两道吧。写完解题报告就睡觉!
这题是简单广度优先搜索,主要是如何建图,把数字在哪一行看作是边,数字和行看作是点,这么一分析立马就能AC了。
首先第一步是建图,我用了两个邻接表(一个也可以)个人认为两个结构清晰一些num对应数字在哪一行,row对应行上有哪些数字。
剩下的就是简单的对于每次查询从源点(查询数字)开始BFS,搜索步数即为答案。
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 vector<int> num[2010], row[110]; 10 int n, m, r, tn, vis[2010][110]; 11 12 struct VEX{ 13 int num, step; 14 }; 15 16 VEX v; 17 18 void init() 19 { 20 for(int i=0; i<2010; i++) num[i].clear(); 21 for(int i=0; i<110; i++) row[i].clear(); 22 } 23 24 int BFS(int x) 25 { 26 queue<VEX> q; 27 v.num = x; 28 v.step = 0; 29 q.push(v); 30 while(!q.empty()) 31 { 32 VEX tv = q.front(); 33 q.pop(); 34 if(tv.num==42) return tv.step; 35 for(vector<int>::iterator ita = num[tv.num].begin(); ita!=num[tv.num].end(); ++ita){ 36 if(vis[tv.num][*ita]==0){ 37 vis[tv.num][*ita] = 1; 38 for(vector<int>::iterator itb = row[*ita].begin(); itb!=row[*ita].end(); ++itb){ 39 if(vis[*itb][*ita]==0){ 40 vis[*itb][*ita] = 1; 41 VEX pv;pv.num = *itb; 42 pv.step = tv.step+1; 43 q.push(pv); 44 } 45 } 46 } 47 } 48 } 49 return -1; 50 } 51 52 int main() 53 { 54 // freopen("in.txt", "r", stdin); 55 56 57 while(scanf("%d%d%d", &n, &m, &r)!=EOF) 58 { 59 init(); 60 for(int i=0; i<n; i++){ 61 for(int j=0; j<m; j++){ 62 scanf("%d", &tn); 63 row[i].push_back(tn); 64 num[tn].push_back(i); 65 } 66 } 67 for(int i=1; i<=r; i++){ 68 memset(vis, 0, sizeof vis); 69 scanf("%d", &tn); 70 printf("%d", BFS(tn)); 71 if(i!=r)printf(" "); 72 } 73 printf(" "); 74 } 75 return 0; 76 }