Code: Select all
AC, lots of missed cases. Should analyze carefully and properly. :(
Code: Select all
1
10 10 2 2
0Code: Select all
Case 1: 9 4Code: Select all
AC, thanks to brianfry713. :)
Code: Select all
1
10 10 2 0
0Code: Select all
Case 1: 13 12Code: Select all
//============================================================================
// Name : .cpp
// Author : AFGhazy
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iomanip>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <limits>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <stdlib.h>
#define INF_SHORT 32767
#define oo 2147483647
#define INF_LL 9223372036854775807
#define INF 2000000000
#define PI acos(-1.0)
#define EPS 1e-9
#define LL long long
#define mod 1000000007
#define pb push_back
#define p push
#define mp make_pair
#define Q queue
#define lp(i, n) for(int i = 0; i < n; i++)
#define rep(i, n) for(int i = 0; i < sizeof(n) / sizeof(n[0]); i++)
#define sz(n) sizeof(n) / sizeof(n[0])
#define vi vector<int >
#define vii vector<vector<int > >
using namespace std;
int main ()
{
int TC, R, C, M, N, W, idx = 0; cin >> TC;
while ( TC-- ) {
int even =0, odd = 0;
int sol[105][105];
memset(sol, 0, 105 * 104);
cin >> R >> C >> M >> N >> W;
int dX[] = {N, M, -N, -M, N, M, -N, -M};
int dY[] = {M, N, -M, -N, -M, -N, M, N};
map<pair<int,int > , bool> Water;
lp(i, W){ int a, b; cin >> a >> b; Water[make_pair(a, b)] = true;}
queue<pair<int, int > > q; q.push(make_pair(0, 0));
map<pair<int, int>, bool> visited;
visited.
visited[make_pair(0, 0)] = true;
while(!q.empty()){
pair<int, int > cur = q.front(); q.pop();
set<pair<int, int > > Sols;
lp(i, 8){
Sols.insert(make_pair(cur.first + dX[i], cur.second + dY[i]));
}
for(set<pair<int, int> >::iterator it = Sols.begin(); it != Sols.end(); it++){
if(it->first >= 0 && it->first < R && it->second >= 0 && it->second < C && !Water[make_pair(it->first, it->second)]){
sol[it->first][it->second]++;
if(!visited[make_pair(it->first, it->second)]){
visited[make_pair(it->first, it->second)] = true;
q.push(make_pair(it->first, it->second));
}
}
}
}
lp(i, R) lp(j, C){
if(sol[i][j] || (!i && !j)){
if(M == 0 || N == 0 || M == N) sol[i][j] /= 2;
if(sol[i][j] % 2) odd++;
else even++;
}
}
cout << "Case " << ++idx << ": " << even << " " << odd << endl;
}
return 0;
}
Code: Select all
6
3 3 2 1
0
4 4 1 2
2
3 3
1 1
10 10 2 2
0
3 3 1 2
2
1 2
2 1
10 10 2 0
0
10 10 0 2
0
Code: Select all
Case 1: 8 0
Case 2: 4 10
Case 3: 9 4
Case 4: 1 0
Case 5: 13 12
Case 6: 13 12
Code: Select all
8 66 29 7
30
2 57
7 59
6 45
5 14
6 35
2 34
3 15
0 64
2 10
7 30
4 12
3 38
0 18
0 47
2 27
2 53
1 21
3 53
3 46
3 3
2 1
4 23
1 56
4 61
4 7
0 20
7 29
4 30
6 38
0 23
AC Output-
1 0
If this is applicable for other grids as well, can somebody please tell how the AC output for below input is 1 0?
Code: Select all
+----------------------+------------------------------------------+
| (0, 0) -> (-29, -7) | X & Y Grid coordinates are off the board |
| (0, 0) -> ( 29, -7) | Y grid coordinate is off the board |
| (0, 0) -> (-29, 7) | X grid coordinate is off the board |
| (0, 0) -> ( 29, 7) | Water specified by input data |
| (0, 0) -> ( -7, -29) | X & Y Grid coordinates are off the board |
| (0, 0) -> ( 7, -29) | Y grid coordinate is off the board |
| (0, 0) -> ( -7, 29) | X grid coordinate is off the board |
| (0, 0) -> ( 7, 29) | Y grid coordinate is off the board |
+----------------------+------------------------------------------+
Code: Select all
#include <bits/stdc++.h>
using namespace std;
#define _CRT_SECURE_NO_DEPRECATE
typedef long long ll ;
typedef vector <int> vi ;
typedef pair <int, int> ii ;
typedef vector <ii> vii;
typedef set <int> si ;
typedef map <string,int> msi;
#define REP(i,a,b) \
for (int i = int (a) ; i <= int (b) ; i++) // a to b , i is local
#define TRvi(c,it) \
for (vi::iterator it = (c).begin () ; it != (c).end () ; it++)
#define TRvii(c,it) \
for (vii::iterator it = (c).begin () ;it !=(c).end () ;it++)
#define TRmsi(c,it) \
for (msi::iterator it = (c).begin () ;it != (c).end () ; it++)
#define INF 2000000000
#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define DFS_WHITE -1
#define DFS_BLACK 1
#define DFS_GRAY 2
#define EPS 1e-9
int row,col,N,M,water[500+7][500+7],visited[500+7][500+7];
bool isValid(ii point){
int x=point.first,y=point.second;
if(x<0||y<0||x>=row||y>=col||water[x][y]==1){
return false;
}
return true;
}
vector<ii> positions(int a,int b){
vector<ii> v;
v.push_back(ii(a-M,b-N));
v.push_back(ii(a-M,N+b));
v.push_back(ii(a+M,b-N));
v.push_back(ii(a+M,N+b));
v.push_back(ii(a-N,b-M));
v.push_back(ii(a-N,b+M));
v.push_back(ii(a+N,b-M));
v.push_back(ii(a+N,M+b));
return v;
}
void dfs(int a,int b){
vector<ii> v=positions(a,b);
int C=0;
set<ii> S;
REP(i,0,v.size()-1){
if(isValid(v[i])){
S.insert(v[i]);
}
}
C=S.size();
if(C%2==0){
visited[a][b]=2;
}
else {
visited[a][b]=1;
}
REP(i,0,v.size()-1){
if(isValid(v[i])){
if(visited[v[i].first][v[i].second]==DFS_WHITE)
dfs(v[i].first,v[i].second);
}
}
}
int main() {
int t,w,x,y;
// freopen("a.txt","r",stdin);
// freopen("b.txt","w",stdout);
scanf("%d",&t);
REP(I,0,t-1){
memset(visited,DFS_WHITE,sizeof visited);
scanf("%d%d%d%d%d",&row,&col,&M,&N,&w);
REP(i,0,w-1){
scanf("%d%d",&x,&y);
water[x][y]=1;
}
dfs(0,0);
int odd=0, even=0;
REP(i,0,row-1) {
REP(j,0,col-1){
if(visited[i][j]==1){
odd++;
}
else if(visited[i][j]==2){
even++;
}
}
}
cout<<"Case "<<I+1<<" : "<<even<<" "<<odd<<endl;
}
return 0;
}