[TIOJ] 1336. 空拍圖
題目連結:http://tioj.infor.org/problems/1336
建中校內補選題,我開賽19分鐘才AC,覺得太廢了QAQ,本題就照著DFS,記得記一下誰已經走過了,走到他就別再走,大概這樣吧
建中校內補選題,我開賽19分鐘才AC,覺得太廢了QAQ,本題就照著DFS,記得記一下誰已經走過了,走到他就別再走,大概這樣吧
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
#define F1(i,a,n) for(int i=a;i<n;i++)
#define F(i,a,n,m) for(int i=a;i<n;i+=m)
#define WC(x) while(x--)
#define N 100
int graph[N+10][N+10];
bitset<N + 10> checked[N + 10];
void check(int,int,int);
int n,m;
char str[N+10];
int main(){
scanf("%d%d",&m,&n);
F1(i,0,n){
scanf("%s",str);
F1(j,0,m){
char c=str[j];
switch(c){
case '-':
graph[i][j]=1;
break;
case 'G':
graph[i][j]=2;
break;
case 'W':
graph[i][j]=3;
break;
case 'B':
graph[i][j]=4;
break;
}
}
}
int G=0,b=0;
F1(i,0,n){
F1(j,0,m){
if(checked[i][j])continue;
if(graph[i][j]>=3){
checked[i][j]=1;
continue;
}
if(graph[i][j]==1)b++;
else if(graph[i][j]==2)G++;
check(i,j,graph[i][j]);
}
}
printf("%d %d",G,b);
return 0;
}
void check(int i,int j,int type){
if(checked[i][j]||graph[i][j]!=type)return;
if(graph[i][j]==type)checked[i][j]=1;
if(i-1>=0)check(i-1,j,type);
if(i+1<n)check(i+1,j,type);
if(j-1>=0)check(i,j-1,type);
if(j+1<m)check(i,j+1,type);
if(i-1>=0&&j-1>=0)check(i-1,j-1,type);
if(i-1>=0&&j+1<m)check(i-1,j+1,type);
if(i+1<n&&j-1>=0)check(i+1,j-1,type);
if(i+1<n&&j+1<m)check(i+1,j+1,type);
}
留言
張貼留言