OJ Board

Code: Select all

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define S 60
enum {LEFT=0,RIGHT,UP,DOWN, VER};
int move[5][2]={	{0,-1},{0,1},{-1,0},{1,0},{0,0} };
int rev[5]={RIGHT,LEFT,DOWN,UP,VER};
bool fnet[S][S][5], vis[S][S][2];
int pre[S][S][2], s, a;

bool in(int x, int y){
	return (x>=1 && x<=s && y>=1 && y<=a);
}

bool bfs(int x, int y){
	queue<int> Q;
	memset(pre,-1,sizeof(pre));
	memset(vis,0,sizeof(vis));
	int u1, v1, w1;
	Q.push(x);
	Q.push(y);
	Q.push(0);
	vis[x][y][0]=true;

	while(!Q.empty()){
		int u=Q.front();Q.pop();
		int v=Q.front();Q.pop();
		int w=Q.front();Q.pop();

		if(w==1 && (u==1 || u==s || v==1 || v==a) ){
			while(pre[u][v][w]!=-1){
				int pr = pre[u][v][w];
				if(w==1)fnet[u][v][pr]=(pr==4);
				else fnet[u+ move[pr][0]][v + move[pr][1]][rev[pr]]=(pr!=4);

				u = u + move[pr][0];
				v = v + move[pr][1];
				w = 1 - w;
			}
			return true;
		}

		for(int i=0;i<5;++i){
			u1 = u + move[i][0];
			v1 = v + move[i][1];
			w1 = 1 - w;

			if( in(u1,v1) && vis[u1][v1][w1]==false ){
				if( (w==0 && fnet[u1][v1][rev[i]]==(i<4) ) || (w==1 && fnet[u][v][i]==(i==4) ) ){
					Q.push(u1);
					Q.push(v1);
					Q.push(w1);
					vis[u1][v1][w1]=true;
					pre[u1][v1][w1]=rev[i];
				}
			}
		}
	}	
	return false;
}

int main (void){
	int T, b;
	int i, j, k;
	int x[S], y[S];
	freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&s,&a,&b);
		for(i=0;i<b;++i)
			scanf("%d%d",&x[i],&y[i]);

		memset( fnet, 0, sizeof( fnet ) );
		
		for(i=0;i<b;++i){
			for(j=0;j<b;++j)
			if(bfs(x[j],y[j])==true)
				break;
			if(j==b)break;
		}
		
		//printf("(flow: %d) ",i);
		if(i<b)printf("not possible\n");
		else printf("possible\n");
	}
	return 0;
}

Code: Select all

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int szx, szy, nbrBanks, nbrNodes, source, sink;
	static int[][] capacity;
	static int[] banks, parent;
	static boolean seen[];
	static Queue<Integer> q;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int nbrTests = scanner.nextInt();
		for (int i = 0; i < nbrTests; i++) {

			szx = scanner.nextInt();
			szy = scanner.nextInt();
			nbrBanks = scanner.nextInt();

			nbrNodes = szx * szy * 2 + 2;
			source = 0;
			sink = nbrNodes - 1;

			banks = new int[nbrNodes];
			seen = new boolean[nbrNodes];
			parent = new int[nbrNodes];
			capacity = new int[nbrNodes][nbrNodes];

			for (int j = 0; j < nbrBanks; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				int index = getIndex(x, y, true);
				banks[index] = 1;
				capacity[0][index] = 1;
			}

			buildGraph();

			if (maxFlow() == nbrBanks)
				System.out.println("possible");
			else
				System.out.println("not possible");
		}
	}

	private static int maxFlow() {

		int maxFlow = 0;
		while (findAugmentingPath()) {
			maxFlow++;
			adjustCapacity();
		}
		return maxFlow;
	}

	private static boolean findAugmentingPath() {
		for (int i = 0; i < nbrNodes; i++) {
			seen[i] = false;
			parent[i] = -1;
		}

		q = new LinkedList<Integer>();
		q.add(source);
		seen[source] = true;

		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int i = 0; i <= sink; i++) {
				if (!seen[i] && capacity[cur][i] > 0) {
					seen[i] = true;
					parent[i] = cur;
					if (i == sink)
						return true;
					q.add(i);
				}
			}
		}
		return false;

	}

	private static void adjustCapacity() {
		int cur = sink;
		int prev = parent[sink];
		while (prev != -1) {
			capacity[prev][cur]--;
			capacity[cur][prev]++;
			cur = prev;
			prev = parent[cur];
		}

	}

	private static void buildGraph() {
		for (int i = 1; i <= szx * 2; i++)
			for (int j = 1; j <= szy; j++) {
				connectNode(i, j);
			}
	}

	private static void connectNode(int x, int y) {
		if (x > szx) {
			capacity[getIndex(x, y, false)][getIndex(x - szx, y, false)] = 1;
		} else {
			if (x == 1 || y == 1 || x == szx || y == szy)
				capacity[getIndex(x, y, false)][nbrNodes - 1] = 1;
			if (x > 1)
				capacity[getIndex(x, y, false)][getIndex(x - 1, y, true)] = 1;
			if (x < szx)
				capacity[getIndex(x, y, false)][getIndex(x + 1, y, true)] = 1;
			if (y > 1)
				capacity[getIndex(x, y, false)][getIndex(x, y - 1, true)] = 1;
			if (y < szy)
				capacity[getIndex(x, y, false)][getIndex(x, y + 1, true)] = 1;
		}
	}

	public static int getIndex(int x, int y, boolean entry) {
		if (entry)
			return szx * szy + (y - 1) * szx + x;
		else if (x > szx)
			return szx * szy + (y - 1) * szx + (x - szx);
		else
			return (y - 1) * szx + x;
	}
}

Code: Select all

         for (int i = 0; i <= sink; i++) {
            if (!seen[i] && capacity[cur][i] > 0) {
               seen[i] = true;
               parent[i] = cur;
               if (i == sink)
                  return true;
               q.add(i);
            }

Code: Select all

2
1 1 1
1 1
5 5 2
2 3
2 3

Code: Select all

possible
not possible

Code: Select all

AC

Code: Select all

10
6 11 28
1 1
1 3
1 4
1 5
1 7
1 9
1 10
1 11
2 1
2 7
2 10
2 11
3 5
3 6
3 9
3 10
4 1
4 4
4 5
4 9
5 5
5 8
5 11
6 4
6 7
6 8
6 9
6 11
16 20 158
1 2
1 5
1 8
1 10
1 11
1 13
1 15
1 16
1 19
1 20
2 1
2 2
2 3
2 4
2 6
2 10
2 11
2 12
2 13
2 14
2 15
2 17
2 19
3 1
3 6
3 8
3 9
3 10
3 14
3 20
4 4
4 5
4 6
4 7
4 8
4 9
4 11
4 14
4 15
4 16
4 18
4 20
5 4
5 5
5 7
5 11
5 14
5 15
5 16
6 2
6 4
6 6
6 12
6 16
6 18
6 19
7 1
7 3
7 4
7 5
7 7
7 9
7 10
7 12
7 13
7 16
8 3
8 6
8 9
8 10
8 14
8 16
8 18
8 19
8 20
9 2
9 4
9 6
9 7
9 9
9 10
9 13
9 16
9 17
9 19
10 2
10 3
10 5
10 6
10 7
10 8
10 10
10 17
10 18
10 20
11 2
11 3
11 4
11 5
11 6
11 10
11 11
11 16
11 17
11 18
11 20
12 3
12 4
12 5
12 6
12 7
12 11
12 13
12 15
12 18
13 2
13 4
13 5
13 9
13 10
13 11
13 13
13 14
13 15
13 19
13 20
14 3
14 4
14 5
14 6
14 7
14 8
14 11
14 12
14 13
14 14
14 16
14 17
14 19
15 1
15 2
15 4
15 6
15 7
15 11
15 13
15 14
15 18
15 19
16 1
16 3
16 4
16 5
16 6
16 10
16 12
16 14
16 19
1 11 6
1 1
1 2
1 3
1 4
1 5
1 6
12 10 72
1 1
1 2
1 3
1 4
1 5
1 9
1 10
2 1
2 2
2 3
2 4
2 7
2 8
2 9
2 10
3 6
3 9
3 10
4 1
4 2
4 6
4 7
5 1
5 2
5 3
5 4
5 7
5 8
5 9
6 2
6 4
6 5
6 8
6 9
6 10
7 1
7 4
7 5
7 6
7 7
7 9
7 10
8 2
8 4
8 7
8 8
8 9
9 1
9 4
9 5
9 6
9 7
9 8
9 9
10 3
10 4
10 5
10 10
11 1
11 4
11 5
11 7
11 8
11 9
11 10
12 1
12 3
12 4
12 5
12 7
12 8
12 9
8 14 53
1 4
1 10
1 13
2 1
2 3
2 5
2 7
2 12
2 13
2 14
3 1
3 2
3 3
3 4
3 5
3 6
3 14
4 2
4 3
4 4
4 5
4 8
4 10
4 11
4 13
5 1
5 2
5 3
5 7
5 8
5 11
6 3
6 5
6 8
6 13
6 14
7 1
7 3
7 5
7 6
7 7
7 8
7 9
7 11
7 12
8 1
8 2
8 4
8 5
8 6
8 8
8 9
8 12
17 16 135
1 1
1 2
1 3
1 4
1 5
1 6
1 10
1 11
1 12
1 13
1 14
2 7
2 8
2 10
2 11
2 13
2 14
2 15
3 3
3 4
3 5
3 6
3 9
3 10
3 11
3 14
3 16
4 3
4 7
4 9
4 13
4 14
4 16
5 3
5 4
5 5
5 6
5 7
5 10
5 14
5 15
6 1
6 8
6 10
6 11
6 15
7 4
7 5
7 6
7 8
7 12
7 13
7 14
7 15
7 16
8 3
8 6
8 10
8 12
8 13
8 15
8 16
9 2
9 3
9 5
9 6
9 7
9 8
9 9
9 10
9 12
9 13
9 16
10 2
10 3
10 6
10 8
10 9
10 10
10 13
10 14
10 16
11 1
11 2
11 3
11 6
11 7
11 8
11 12
12 1
12 5
12 7
12 9
12 10
12 11
12 14
12 16
13 2
13 3
13 6
13 7
13 8
13 9
13 12
13 14
13 15
14 1
14 2
14 5
14 6
14 7
14 8
14 11
14 13
14 14
14 16
15 1
15 2
15 3
15 4
15 8
15 10
15 12
15 14
15 15
15 16
16 2
16 3
16 7
16 12
16 16
17 2
17 6
17 11
17 15
10 13 64
1 2
1 3
1 4
1 5
1 6
1 9
1 12
1 13
2 2
2 3
2 4
2 5
2 7
2 8
2 10
2 11
2 13
3 1
3 2
3 4
3 8
4 1
4 4
4 5
4 6
4 10
4 11
4 12
5 1
5 3
5 6
5 7
5 10
6 3
6 8
6 9
6 10
6 12
7 3
7 4
7 5
7 7
7 10
7 11
7 13
8 1
8 2
8 8
8 9
8 10
8 11
8 12
9 1
9 2
9 5
9 7
9 9
10 1
10 4
10 5
10 6
10 8
10 9
10 13
6 8 24
1 1
1 3
1 5
1 6
2 1
2 2
2 5
2 6
3 4
3 6
3 7
3 8
4 1
4 3
4 4
4 5
5 1
5 2
5 6
5 7
5 8
6 2
6 3
6 6
11 1 8
1 1
3 1
4 1
5 1
7 1
8 1
9 1
11 1
8 8 34
1 3
1 4
1 8
2 1
2 2
2 4
2 7
3 2
3 6
3 7
3 8
4 7
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 7
6 8
7 1
7 2
7 3
7 7
8 1
8 2
8 3
8 4
8 5
8 7

Code: Select all

not possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
possible
not possible