【题解】狼和羊-C++
Description 9 12 .###.#####.. #.oo#...#v#. #..o#.#.#.#. #..##o#...#. #.#v#o###.#. #..#v#....#. #...v#v####. .####.#vv.o# .......####. Sample Output 3 5 这道题目emm,虽然是BFS的 水 题,但是有一个点卡了我很久。
最后才发现,我的代码里面计数并变成#的这一板块是放在bfs里while的开头,也就是当处理队头的时候才计数变#,所以就TLE,… #include<bits/stdc++.h> using namespace std; int n,m; int lang,yang;//awa char mp[258][258]; struct node { int x,y; }; int dir[4][2]={{1,0},{-1,{0,1},-1}}; void bfs(int x,int y) { int nl=0,ny=0;//now_lang,now_yang queue<node> q; q.push((node){x,y}); if(mp[x][y]=='o')ny++; else if(mp[x][y]=='v')nl++; mp[x][y]='#'; while(!q.empty()) { node now=q.front(); q.pop(); for(int i=0;i<4;i++) { int tx=now.x+dir[i][0],ty=now.y+dir[i][1]; if(mp[tx][ty]!='#'&&1<=tx&&tx<=n&&1<=ty&&ty<=m) { q.push((node){tx,ty}); if(mp[tx][ty]=='o')ny++; else if(mp[tx][ty]=='v')nl++; mp[tx][ty]='#'; } } } if(ny>nl)yang+=ny; else lang+=nl; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>mp[i][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]!='#')bfs(i,j); // for(int i=1;i<=n;i++) // { // for(int j=1;j<=m;j++) // { // cout<<mp[i][j]; // } // cout<<endl; // } cout<<yang<<" "<<lang<<endl; return 0; } p.s. 惨不忍睹的部分请自行跳过awa (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |