Samsung Interview Question
fresherssCountry: India
Interview Type: Written Test
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception {
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception {
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception {
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception {
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
int count_number(int **arr,int r,int c,int pos_r,int pos_c,int length){
if(length <= 1) return length;
int up[] = {0,1,1,0,1,0,0,1};
int down[] = {0,1,1,0,0,1,1,0};
int left[] = {0,1,0,1,0,0,1,1};
int right[] = {0,1,0,1,1,1,0,0};
bool **visited = new bool*[r];
for(int i=0;i<r;i++){
visited[i] = new bool[c];
for(int j=0;j<c;j++) visited[i][j] = false;
}
int level = 1;
int count = 0;
queue<pair<int,int>> q1;
q1.push(make_pair(pos_r,pos_c));
visited[pos_r][pos_c] = true;
q1.push(make_pair(INT_MIN,INT_MIN));
while(!q1.empty()){
if(level > length) break;
pair<int,int> temp = q1.front();
q1.pop();
if(temp.first == INT_MIN && temp.second == INT_MIN){
if(q1.empty()) break;
level++;
q1.push(make_pair(INT_MIN,INT_MIN));
}else{
count ++;
int val = arr[temp.first][temp.second];
int row = temp.first,col = temp.second;
//cout<<row<<","<<col<<endl;
//For up
if(up[val] == 1 && row-1>=0 && arr[row-1][col] != 0 && !visited[row-1][col] && down[arr[row-1][col]]){
q1.push(make_pair(row-1,col));
visited[row-1][col] = true;
}
//For down
if(down[val] == 1 && row+1<r && arr[row+1][col] != 0 && !visited[row+1][col] && up[arr[row+1][col]]){
q1.push(make_pair(row+1,col));
visited[row+1][col] = true;
}
//For left
if(left[val] == 1 && col-1>=0 && arr[row][col-1] != 0 && !visited[row][col-1] && right[arr[row][col-1]]){
q1.push(make_pair(row,col-1));
visited[row][col-1] = true;
}
//For right
if(right[val] == 1 && col+1<c && arr[row][col+1] != 0 && !visited[row][col+1] && left[arr[row][col+1]]){
q1.push(make_pair(row,col+1));
visited[row][col+1] = true;
}
}
}
return count;
}
int main() {
int test = 0;
cin>>test;
for(int i=0;i<test;i++){
int r = 0, c = 0, pos_r=0,pos_c= 0,length = 0;
cin>>r>>c>>pos_r>>pos_c>>length;
int **arr = new int*[r];
for(int j=0;j<r;j++){
arr[j] = new int[c];
}
for(int j=0;j<r;j++){
for(int k=0;k<c;k++){
cin>>arr[j][k];
}
}
cout<<count_number(arr,r,c,pos_r,pos_c,length)<<endl;
}
}
import java.util.*;
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception{
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
import java.util.*;
class endoScope {
public static Scanner scn = new Scanner(System.in);
public static void main(String args[]) throws Exception{
int T = scn.nextInt();
while (T-- > 0) {
int N = scn.nextInt();
int M = scn.nextInt();
int R = scn.nextInt();
int C = scn.nextInt();
int L = scn.nextInt();
int[][] Maze = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Maze[i][j] = scn.nextInt();
}
}
boolean[][] visit = new boolean[N][M];
int[][] dist = new int[N][M];
int[] up = { 0, 1, 1, 0, 1, 0, 0, 1 };
int[] down = { 0, 1, 1, 0, 0, 1, 1, 0 };
int[] left = { 0, 1, 0, 1, 0, 0, 1, 1 };
int[] right = { 0, 1, 0, 1, 1, 1, 0, 0 };
myQueue Q = new myQueue();
if(Maze[R][C] != 0){
Q.add(new Pair(R, C));
visit[R][C] = true;
dist[R][C] = 1;
}
while (!Q.isEmpty()) {
Pair elem = Q.remove();
int x = elem.x;
int y = elem.y;
if (x - 1 >= 0 && up[Maze[x][y]] == 1 && down[Maze[x - 1][y]] == 1 && !visit[x - 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x - 1, y));
visit[x - 1][y] = true;
dist[x - 1][y] = d;
}
}
if (x + 1 < N && down[Maze[x][y]] == 1 && up[Maze[x + 1][y]] == 1 && !visit[x + 1][y]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x + 1, y));
visit[x + 1][y] = true;
dist[x + 1][y] = d;
}
}
if (y - 1 >= 0 && left[Maze[x][y]] == 1 && right[Maze[x][y - 1]] == 1 && !visit[x][y - 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y - 1));
visit[x][y - 1] = true;
dist[x][y - 1] = d;
}
}
if (y + 1 < M && right[Maze[x][y]] == 1 && left[Maze[x][y + 1]] == 1 && !visit[x][y + 1]) {
int d = dist[x][y] + 1;
if (d <= L) {
Q.add(new Pair(x, y + 1));
visit[x][y + 1] = true;
dist[x][y + 1] = d;
}
}
}
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (dist[i][j] > 0) {
count++;
}
}
}
System.out.println(count);
}
}
static class myQueue {
Pair[] Q = new Pair[1000000];
int front;
int rear;
myQueue() {
front = 0;
rear = 0;
}
public void add(Pair el) {
Q[rear++] = el;
}
public Pair remove() {
return Q[front++];
}
public boolean isEmpty() {
return front == rear;
}
}
static class Pair {
int x;
int y;
Pair(int x1, int y1) {
this.x = x1;
this.y = y1;
}
}
}
}
#include<iostream>
using namespace std;
int pipes[8][4]={{0,0,0,0},{1,1,1,1},{0,1,0,1},{1,0,1,0},{0,1,1,0},{0,0,1,1},{1,0,0,1},{1,1,0,0}};
bool valid(int i,int j,int n,int m)
{
if(i<0 || i>=n ||j<0 ||j>=m)
return false;
return true;
}
bool connected(int x,int y,int i)
{
if(x==0 || y==0)
return false;
if(pipes[x][i]==1 && pipes[y][(i+2)%4]==1)
return true;
return false;
}
int qt[1000010][3];
int main()
{
int t;
cin >>t;
while(t--)
{
int front=0;
int rear=0;
int n,m;
cin >>n>>m;
int i,j;
int dir1[4]={0,-1,0,1};
int dir2[4]={-1,0,1,0};
int a[n][m];
bool visited[n][m];
int c,b,l,x,y,z;
cin >> c>>b>>l;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin >>a[i][j];
visited[i][j]=false;
}
}
qt[rear][0]=c;
qt[rear][1]=b;
qt[rear][2]=1;
visited[c][b]=true;
rear++;
long long int ans=0;
while(front!=rear)
{
x=qt[front][0];
y=qt[front][1];
z=qt[front][2];
// cout << x<<" "<<y<<endl;
front++;
//visited[x][y]=true;
if(a[x][y]==0)
continue;
ans++;
if(z==l)
continue;
for(i=0;i<4;i++)
{
int ni=x+dir1[i];
int nj=y+dir2[i];
if(valid(ni,nj,n,m) && !visited[ni][nj])
{
if(connected(a[x][y],a[ni][nj],i))
{
visited[ni][nj]=true;
qt[rear][0]=ni;
qt[rear][1]=nj;
qt[rear][2]=z+1;
rear++;
}
}
}
}
cout << ans<<endl;
}
return 0;
}
sample input ?
- sks September 06, 2018