NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemF-捷運路線

作者 主題: ProblemF-捷運路線  (閱讀 1367 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
ProblemF-捷運路線
« 於: 十二月 12, 2013, 06:36:33 pm »

無向無環圖->tree
對於每一棵tree,他的最少捷運路線就是[(leaf數+1)/2]
(可以證 但是這裡不證)
但是我比賽的時候完全沒有想過他有可能是forest......Orz
----------------
NPSC2013官網公布測資了
官測AC。
----------------
代碼: [選擇]
#include <iostream>
#include <cstring>
#include <deque>
#define max_N 110
#define isStation(x) (x!='.'&&x!='#')
using namespace std;
char mp[max_N][max_N];
bool v[max_N][max_N];
int vec[4][2]=
{
{0,-1},
{-1,0},
{0,1},
{1,0}
};
typedef struct point{int x,y;} PT;
deque<PT > Q;
int isLeaf(PT v)
{
int ret=0;
for(int i=0;i<4;i++)
ret+=(mp[v.x+vec[i][0]][v.y+vec[i][1]]=='#'?1:0);
if(ret==1)
return 1;
return 0;
}
int BFS(PT S)
{
Q.clear();
int ret=0;
Q.push_back(S);
v[S.x][S.y]=true;
while(!Q.empty())
{
if(isStation(mp[Q[0].x][Q[0].y]))
ret+=isLeaf(Q[0]);
for(int i=0;i<4;i++)
{
if(mp[Q[0].x+vec[i][0]][Q[0].y+vec[i][1]]!='.'&&!v[Q[0].x+vec[i][0]][Q[0].y+vec[i][1]])
{
v[Q[0].x+vec[i][0]][Q[0].y+vec[i][1]]=true;
Q.push_back((PT){Q[0].x+vec[i][0],Q[0].y+vec[i][1]});
}
}
Q.pop_front();
}
return ret;
}
int main()
{
int T,N,M;
cin>>T;
while(T--)
{
cin>>N>>M;
memset(mp,'.',sizeof(mp));
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
cin>>mp[i][j];
memset(v,false,sizeof(v));
int ans=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
if(mp[i][j]=='#'&&!v[i][j])
ans+=((BFS((PT){i,j})+1)/2);
cout<<ans<<endl;
}
return 0;
}
« 上次編輯: 十二月 13, 2013, 11:58:53 pm 由 darry140 »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2013國中組決賽
 ProblemF-捷運路線