#16047: 測試都OK卻不會過?


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [163.20.185.250]
最後登入時間 :
2024-03-15 09:17:14
d165. 八、草场普查 -- NOI冬令营 | From: [220.133.124.235] | 發表日期 : 2018-11-14 21:48

#include <iostream>
#include <algorithm>
using namespace std;
int maze[105][105];
int n,m,ct=0; //草場個數
int A[105]; //草場面積
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
//---------------------------------------------------
void pW(){ //測試用
int i,j;
for(i=0; i<n; i++){
for(j=0; j<m; j++) cout<<maze[i][j]<<" ";
cout<<endl;
}
cout<<"---------------------\n";
}
//---------------------------------------------------
void dfs(int x, int y){
int xx,yy;
//pW();
for(int i=0; i<4; i++){
xx=x+dx[i]; yy=y+dy[i];
if(xx>=0 && xx<m && yy>=0 && yy<n){
if(maze[yy][xx]>0){
A[ct] += maze[yy][xx]; //面積累加
maze[yy][xx]=-1;
dfs(xx,yy); //遞迴
}
}
}
}
//==================================================
int main(){
cin>>n>>m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) cin>>maze[i][j];
//pW();
for(int yy=0; yy<n; yy++){
for(int xx=0; xx<m; xx++){
if(maze[yy][xx]>0) {
ct++; //草場數目+1
A[ct]=maze[yy][xx]; //該區域面積開始累加
maze[yy][xx]=-1;
dfs(xx,yy); //計算草場面積,0改成-1
//pW();
}
}
}

cout<<ct<<endl;
sort(A+1, A+ct+1);
//for(int i=1; i<=ct; i++) cout<<A[i]<<" ";
cout<<A[ct];
}

 

請指教

 

 
#16051: Re:測試都OK卻不會過?


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.32.12]
最後登入時間 :
2024-04-25 19:27:08
d165. 八、草场普查 -- NOI冬令营 | From: [140.113.208.181] | 發表日期 : 2018-11-14 23:15

原文吃掉,稍微看一下DFS好像沒問題

但是要找到最大面積時不應該使用 Sort

如果你沒有AC是因為被 Kill 的話可能就是Sort找最大面積的這個方法耗費太多時間了

 
 
ZeroJudge Forum