11906 - Knight in a War Grid

[SHOJIBcuet09]

check the input ..

1
3 3 1 2
2
1 2
2 1
AC output
Case 1: 1 0

I was getting WA for output : "Case 1: 0 0" (problem description is saying this, I think but this was WA for at least 6 times)

[pranon]

``Wrong Answer"! :'(
Can anyone help me in finding my mistake?

Code: Select all

AC, lots of missed cases. Should analyze carefully and properly. :(

[brianfry713]

Input:

Code: Select all

1
10 10 2 2
0

AC Output:

Code: Select all

Case 1: 9 4

[pranon]

Code edited for above input. But... is still being judged ``Wrong Answer".

Code: Select all

AC, thanks to brianfry713. :)

Sorry. And thanks in advance.

[brianfry713]

Input:

Code: Select all

1
10 10 2 0
0

AC Output:

Code: Select all

Case 1: 13 12

[AFGhazy]

Code: 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;
}

I don't know why it give me 7 times WA

[brianfry713]

That code won't compile. Remove line 64: visited.

Try input:

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

AC output:

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

[antonydeepak]

1
3 3 1 2
2
1 2
2 1
AC output
Case 1: 1 0

How is the answer 1 0 for this case. If I understand the problem correctly, the knight will not be able to make a single move (because of the water) and hence it should be 0 0 right? Help appreciated.

[anando_du]

#to_deepak
here 0,0 grid is marked as even . so if u get no answer (odd = 0 && even =0 ) then still your answer would be 1 0 .

[mehrab2603]

Getting WA. May I get some test cases?
Edit: solved

Code: Select all

//code removed after AC

[samir_h]

About water: For a single move
1. Just start position and end position need to consider
2. No need to consider the whole path(alternate paths etc.)

Need to calculate neighbors carefully.
Special cases: M = N, N or M = 0...

[wrangler]

I have a doubt about the problem-
1) if grid(0,0) count is 0, i.e. cannot be reachable from any other grid should this be counted as even, or neither odd nor even?
2) if any other grid(x,y) count is 0, i.e. cannot be reachable from any other grid should this also be counted as even, or neither odd nor even?
Somebody already answered saying if grid(0,0) count is 0 it should be marked as even. Is this applicable only for grid(0,0) or for other grids also?
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

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

[pointless0]

Regarding the count of zero at (0,0)... "start" != "visit".

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       |
+----------------------+------------------------------------------+

Knight starts at (0, 0), visits no squares, ends at (0, 0). For all the squares reached by the knight, count the numbers specified in the problem statement. We have only a "0" resulting from the knight reaching (0, 0). "0" is an even number, so our result is "1 0".

[civilguy]

Getting Wrong Answer.

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;
}