11906 - Knight in a War Grid

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
SHOJIBcuet09
New poster
Posts: 1
Joined: Sun Apr 01, 2012 2:44 am

11906 - Knight in a War Grid

Post by SHOJIBcuet09 » Tue Apr 03, 2012 5:45 am

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
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 11906 - Knight in a War Grid

Post by pranon » Tue Jul 24, 2012 8:00 pm

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

Code: Select all

AC, lots of missed cases. Should analyze carefully and properly. :(
Last edited by pranon on Thu Jul 26, 2012 11:41 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11906 - Knight in a War Grid

Post by brianfry713 » Wed Jul 25, 2012 2:15 am

Input:

Code: Select all

1
10 10 2 2
0
AC Output:

Code: Select all

Case 1: 9 4
Check input and AC output for thousands of problems on uDebug!

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 11906 - Knight in a War Grid

Post by pranon » Wed Jul 25, 2012 9:19 am

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

Code: Select all

AC, thanks to brianfry713. :)

Sorry. And thanks in advance.
Last edited by pranon on Thu Jul 26, 2012 11:42 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11906 - Knight in a War Grid

Post by brianfry713 » Thu Jul 26, 2012 12:00 am

Input:

Code: Select all

1
10 10 2 0
0
AC Output:

Code: Select all

Case 1: 13 12
Check input and AC output for thousands of problems on uDebug!

AFGhazy
New poster
Posts: 1
Joined: Sat Jun 28, 2014 2:17 am

11906

Post by AFGhazy » Sat Jun 28, 2014 2:26 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11906

Post by brianfry713 » Tue Jul 08, 2014 2:03 am

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
Check input and AC output for thousands of problems on uDebug!

antonydeepak
New poster
Posts: 2
Joined: Sun Mar 08, 2015 10:25 am

Re: 11906 - Knight in a War Grid

Post by antonydeepak » Fri Mar 20, 2015 9:05 am

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
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 11906 - Knight in a War Grid

Post by anando_du » Thu Apr 23, 2015 8:25 pm

#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
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 11906 - Knight in a War Grid

Post by mehrab2603 » Mon Aug 24, 2015 10:24 am

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

Code: Select all

//code removed after AC

samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

11906 - Knight in a War Grid

Post by samir_h » Fri Mar 11, 2016 8:47 am

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
New poster
Posts: 1
Joined: Mon Apr 04, 2016 8:32 pm

Re: 11906 - Knight in a War Grid

Post by wrangler » Sun May 08, 2016 7:53 pm

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
New poster
Posts: 9
Joined: Wed Jan 13, 2016 3:24 am

Re: 11906 - Knight in a War Grid

Post by pointless0 » Thu May 19, 2016 6:05 pm

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
New poster
Posts: 1
Joined: Thu Nov 05, 2015 9:01 am
Location: BUET
Contact:

Re: 11906 - Knight in a War Grid

Post by civilguy » Wed Aug 31, 2016 10:15 pm

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

Post Reply

Return to “Volume 119 (11900-11999)”