[TIOJ] 1336. 空拍圖

題目連結:http://tioj.infor.org/problems/1336
建中校內補選題,我開賽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);
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology