1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:

#include <iostream>
#include <fstream>

//Eingabeformat:
//2 Zahlen fuer die Feldgröße
//horizontale Zeile mit der Anzahl der '-'
//horizontale Zeile mit der Anzahl der '+'
//vertikale Spalte mit der Anzahl der '-'
//vertikale Spalte mit der Anzahl der '+'
//m Zeilen mit n Zeichen, die das Feld beschreiben
//Man beschreibt, in welcher Richtung der andere Teil der Magnetplatte liegt
//ob nach Osten, Süden, Westen od Norden: e, s, w, n

const int MAX_X = 12;
const int MAX_Y = 12;

std::ofstream aus("sol.txt");

char board[MAX_X + 2][MAX_Y + 2]; //Die Arrays sind etwas größer, um auch Abfragen außerhalb des Feldes stellen zu können
int pol_x[MAX_X + 2][MAX_Y + 2]; //bewirkt weniger Fallunterscheidungen: bin am Rand, zu weit oben, zu weit links, ...
int pol_y[MAX_X + 2][MAX_Y + 2];

int rem_cm[MAX_X + 2], rem_cp[MAX_X + 2], rem_cn[MAX_X + 2]; //Gibt die Anzahl an Werten von '-', '+' u. 'n' an, die man noch vergeben darf
int rem_rm[MAX_Y + 2], rem_rp[MAX_Y + 2], rem_rn[MAX_Y + 2]; //c .. Spalte, r .. Reihe; m .. '-', p .. '+', n ..'n'

int n, m;

void besetze(int x, int y);
void ende();
void output(); //fürs Debuggen

int main(int argc, char *argv[])
{
   std::ifstream ein(argv[1]); //Eingabedatei als Argument übergeben bitte
   int i, j; char c;

   ein >> n >> m;

   for(i = 1; i <= n; i++)
      ein >> rem_cm[i];
   for(i = 1; i <= n; i++)
      ein >> rem_cp[i];
   for(i = 1; i <= m; i++)
      ein >> rem_rm[i];
   for(i = 1; i <= m; i++)
      ein >> rem_rp[i];

   for(i = 1; i <= n; i++)
      rem_cn[i] = m - rem_cm[i] - rem_cp[i];
   for(i = 1; i <= m; i++)
      rem_rn[i] = m - rem_rm[i] - rem_rp[i];

   for(i = 1; i <= m; i++)
   {
      for(j = 1; j <= n; j++)
      {
         ein >> c;
         switch(c)
         {
            case 'e': pol_x[j][i] = j + 1; pol_y[j][i] = i; break;
            case 's': pol_x[j][i] = j; pol_y[j][i] = i + 1; break;
            case 'w': pol_x[j][i] = j - 1; pol_y[j][i] = i; break;
            case 'n': pol_x[j][i] = j; pol_y[j][i] = i - 1; break;
         }
      }
   }

   besetze(1, m);

   return 0;
}

void besetze(int x, int y)
{
   //bewege dich von unten links nach oben rechts;
   //erst horizontal, dann vertikal
   //(0;MAX_Y)->(MAX_X;0)

   if(x > n) //Zeile zu ende
   {
      x = 1;
      y--;

      if(y == 0) //Ergebnis gefunden!!!
      {
         ende();
         return;
      }
   }

   if(board[x][y] != 0) //Diese Zelle hat bereits einen fixen Wert
   {
      besetze(x + 1, y);
      return;
   }

   int px = pol_x[x][y], py = pol_y[x][y];

   //versuche mit einem '-' zu besetzen
   if(board[x-1][y] != '-' && board[x][y+1] != '-' && //Keine '-' benachbart
      board[x+1][y] != '-' && board[x][y-1] != '-' &&
      board[px - 1][py] != '+' && //Gegenpol hat keine '+' benachbart
      board[px][py + 1] != '+' &&
      board[px + 1][py] != '+' &&
      board[px][py - 1] != '+' &&
      rem_rm[y] > 0 && rem_cm[x] > 0 && //Es gibt noch '-' zu vergeben
      rem_rp[py] > 0 && rem_cp[px] > 0) //Es gibt auch noch '+' zu vergeben
   {
      board[x][y] = '-'; board[px][py] = '+'; //ins Brett eintragen
      rem_rm[y]--; rem_cm[x]--;
      rem_rp[py]--; rem_cp[px]--;

      besetze(x + 1, y);

      board[x][y] = 0; //alle Eintraege wieder loeschen
      board[px][py] = 0;
      rem_rm[y]++;
      rem_cm[x]++;
      rem_rp[py]++;
      rem_cp[px]++;
   }

   //versuche mit einem '+' zu besetzen
   if(board[x-1][y] != '+' && board[x][y+1] != '+' && //Keine '+' benachbart
      board[x+1][y] != '+' && board[x][y-1] != '+' &&
      board[px - 1][py] != '-' && board[px][py + 1] != '-' && //Gegenpol hat keine '-' benachbart
      board[px + 1][py] != '-' && board[px][py - 1] != '-' &&
      rem_rp[y] > 0 && rem_cp[x] > 0 && //Es gibt noch '+' zu vergeben
      rem_rm[py] > 0 && rem_cm[px] > 0) //Es gibt auch noch '-' zu vergeben
   {
      board[x][y] = '+'; board[px][py] = '-'; //ins Brett eintragen
      rem_rp[y]--; rem_cp[x]--;
      rem_rm[py]--; rem_cm[px]--;

      besetze(x + 1, y);

      board[x][y] = 0; board[px][py] = 0;//alle Eintraege wieder loeschen
      rem_rp[y]++; rem_cp[x]++;
      rem_rm[py]++; rem_cm[px]++;
   }

   //versuche mit einem 'n' zu besetzen
   if(rem_rn[y] > 0 && rem_cn[x] > 0 && //Es gibt noch 'n' zu vergeben
      rem_rn[py] > 0 && rem_cn[px] > 0) //Es gibt auch noch 'n' zu vergeben
   {
      board[x][y] = 'n'; //ins Brett eintragen
      board[px][py] = 'n';
      rem_rn[y]--;
      rem_cn[x]--;
      rem_rn[py]--;
      rem_cn[px]--;

      besetze(x + 1, y);

      board[x][y] = 0; //alle Eintraege wieder loeschen
      board[px][py] = 0;
      rem_rn[y]++;
      rem_cn[x]++;
      rem_rn[py]++;
      rem_cn[px]++;
   }

}

void ende()
{
   int i, j;
   for(i = 1; i <= m ; i++)
   {
      for(int j = 1; j <= n; j++)
         aus << board[j][i];
      aus << endl;
   }
   aus << endl;
}

void output()
{
   int i, j;

   cout << "   ";
   for(i = 1; i <= n; i++)
      cout << rem_cm[i];
   cout << "\n   ";
   for(i = 1; i <= n; i++)
      cout << rem_cp[i];
   cout << "\n   ";
   for(i = 1; i <= n; i++)
      cout << rem_cn[i];
   cout << endl;
   for(i = 1; i <= m ; i++)
   {
      cout << rem_rm[i] << rem_rp[i] << rem_rn[i];
      for(int j = 1; j <= n; j++)
         cout << board[j][i];
      cout << endl;
   }
}