#265158 (C++11) No.697 池の数はいくつか

• 問題: No.697 池の数はいくつか
• ユーザー: amtgjw
• 提出日時: 2018-06-13 10:43:29
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,165 bytes
• コンパイル時間: 904 ms
• コンパイル使用メモリ: 69,156 KB
• 実行使用メモリ: 38,528 KB
• 最終ジャッジ日時: 2024-11-25 13:34:55
• 合計ジャッジ時間: 11,898 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,820 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	2 ms; 6,824 KB
testcase_04	AC	1 ms; 6,820 KB
testcase_05	AC	1 ms; 6,816 KB
testcase_06	AC	2 ms; 6,820 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	1 ms; 6,820 KB
testcase_09	AC	1 ms; 6,820 KB
testcase_10	AC	1 ms; 6,820 KB
testcase_11	WA	-
testcase_12	AC	1 ms; 6,820 KB
testcase_13	AC	1 ms; 6,820 KB
testcase_14	AC	1 ms; 6,820 KB
testcase_15	AC	1 ms; 6,820 KB
testcase_16	AC	2 ms; 6,816 KB
testcase_17	AC	1 ms; 6,820 KB
testcase_18	AC	1 ms; 6,816 KB
testcase_19	AC	1 ms; 6,820 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	2 ms; 6,820 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	AC	1,308 ms; 38,400 KB
testcase_30	WA	-
testcase_31	AC	1,336 ms; 38,528 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-

ソースコード

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)
#define PER(i,n)	for(int i=0;i>(n);--i)
#define PERS(i,s,t)	for(int i=(s);i>(t);--i)

#define INF 		2000000007
#define MINF		-200000007
#define MOD			17 	
// 2^20

#define MAX 		200005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) is >> x;
  //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいいです。
  return is;
}

//int dp[MAX];
int H,W;
int cnt;
int dis;
void check(vector<vector<int> > &A,int y,int x){
	if(A[y][x]==0)return;
	int n = (y!=0) ? A[y-1][x] : 0;
	int w = (x!=0) ? A[y][x-1] : 0;
	if(n!=0&&w!=0){
		A[y][x] = min(n,w);
		if(n!=w)
			++dis;
	}
	else if(n==0&&w==0)
		A[y][x] = ++cnt;
	else
		A[y][x] = n+w;
}

int main(){
	cin>>H>>W;

	vector<vector<int> > A(H,vector<int>(W,false));
	cin>>A;

	REP(i,H)
		REP(j,W)
			check(A,i,j);
	cout << (cnt-dis) << endl;

	return 0;
}