Sachverhalt: Sachverhalt: A. B._ ist Eigentümer des südlich von Altendorf ausserhalb der Bauzone gelegenen Grundstücks Kat. Nr. 422, Cholrisi/Vorderbergstrasse. Auf dieser Parzelle stehen ein vom Ehepaar B._ bewohntes Wohnhaus sowie ein Schopfgebäude. Der Gemeinderat Altendorf hatte seinerzeit am 10. Juli 1981 eine "Aufstockung des Holzschopfes" unter der Auflage bewilligt, dass dieser nicht zu Wohnzwecken ausgebaut werde. Eine Bewilligung des kantonalen Amtes für Raumplanung wurde nicht eingeholt. Im Juni 2000 reichte B._ ein Baugesuch für verschiedene kleinere Bauvorhaben auf seinem Grundstück ein, darunter für die im Obergeschoss des Schopfes bereits eingebaute Werkstatt sowie für eine neu zu erstellende Zufahrt zum Schopf. Gegen diese Bauvorhaben erhoben die Nachbarn, die Eheleute A._, Einsprache. A. B._ ist Eigentümer des südlich von Altendorf ausserhalb der Bauzone gelegenen Grundstücks Kat. Nr. 422, Cholrisi/Vorderbergstrasse. Auf dieser Parzelle stehen ein vom Ehepaar B._ bewohntes Wohnhaus sowie ein Schopfgebäude. Der Gemeinderat Altendorf hatte seinerzeit am 10. Juli 1981 eine "Aufstockung des Holzschopfes" unter der Auflage bewilligt, dass dieser nicht zu Wohnzwecken ausgebaut werde. Eine Bewilligung des kantonalen Amtes für Raumplanung wurde nicht eingeholt. Im Juni 2000 reichte B._ ein Baugesuch für verschiedene kleinere Bauvorhaben auf seinem Grundstück ein, darunter für die im Obergeschoss des Schopfes bereits eingebaute Werkstatt sowie für eine neu zu erstellende Zufahrt zum Schopf. Gegen diese Bauvorhaben erhoben die Nachbarn, die Eheleute A._, Einsprache. B. Mit Verfügung vom 8. Juni 2001 erteilte das kantonale Amt für Raumplanung des Kantons Schwyz dem im Jahre 1981 von der Gemeinde bewilligten Holzschopfaufbau eine nachträgliche Raumplanungsbewilligung unter der Auflage, dass dieser weder zu wohn- noch zu gewerblichen Zwecken ausgebaut werden dürfe. Eine nachträgliche Ausnahmebewilligung für den Einbau der Werkstatt im Obergeschoss wurde dagegen verweigert. Der Baugesuchsteller wurde angewiesen, die nicht bewilligten Fenster auf der West-, Ost- und Südseite des Holzschopfes innert sechs Monaten nach Rechtskraft der Verfügung zu entfernen und die Öffnungen mit einer Holzschalung zu versehen. Sämtliche Werkstatteinrichtungen, namentlich die Hobel- und Bohrmaschinen sowie die Bandsäge, seien abzumontieren. Der Grundeigentümer wurde weiter verpflichtet, das bisher im Freien, auf einer - ebenfalls nicht bewilligten und daher abzubrechenden - Holzplattform aufgestapelte Holz im Holzschopf zu lagern. Im Übrigen verweigerte das kantonale Amt auch eine Ausnahmebewilligung für die Erstellung einer neuen Zufahrt zum Schopf. Diese Verfügung des kantonalen Amtes wurde dem Gesuchsteller und den Einsprechern am 29. Juni 2001 vom Gemeinderat Altendorf eröffnet. Die Einsprecher gelangten hierauf mit Beschwerde an den Regierungsrat des Kantons Schwyz. Dieser hiess die Beschwerde mit Beschluss vom 10. Dezember 2003 gut und änderte die Verfügung des kantonalen Amtes für Raumplanung in dem Sinne ab, dass die nachträgliche Ausnahmebewilligung für das Schopfgebäude auf der Parzelle Kat. Nr. 422 verweigert werde. Das gesamte Schopfgebäude sei innert 12 Monaten ab Rechtskraft des Regierungsratsentscheides abzubrechen und das Terrain entsprechend dem ursprünglichen Zustand wiederherzustellen und zu renaturieren. B._ wandte sich hierauf seinerseits an das Verwaltungsgericht des Kantons Schwyz, das am 11. März 2004 den angefochtenen Regierungsratsbeschluss in Gutheissung der Beschwerde aufhob und die Verfügung des Amtes für Raumplanung vom 8. Juni 2001 bestätigte, soweit diese vom Regierungsrat abgeändert worden war. Diese Verfügung des kantonalen Amtes wurde dem Gesuchsteller und den Einsprechern am 29. Juni 2001 vom Gemeinderat Altendorf eröffnet. Die Einsprecher gelangten hierauf mit Beschwerde an den Regierungsrat des Kantons Schwyz. Dieser hiess die Beschwerde mit Beschluss vom 10. Dezember 2003 gut und änderte die Verfügung des kantonalen Amtes für Raumplanung in dem Sinne ab, dass die nachträgliche Ausnahmebewilligung für das Schopfgebäude auf der Parzelle Kat. Nr. 422 verweigert werde. Das gesamte Schopfgebäude sei innert 12 Monaten ab Rechtskraft des Regierungsratsentscheides abzubrechen und das Terrain entsprechend dem ursprünglichen Zustand wiederherzustellen und zu renaturieren. B._ wandte sich hierauf seinerseits an das Verwaltungsgericht des Kantons Schwyz, das am 11. März 2004 den angefochtenen Regierungsratsbeschluss in Gutheissung der Beschwerde aufhob und die Verfügung des Amtes für Raumplanung vom 8. Juni 2001 bestätigte, soweit diese vom Regierungsrat abgeändert worden war. C. Die Eheleute A._ haben gegen das Urteil des Verwaltungsgerichtes des Kantons Schwyz Verwaltungsgerichtsbeschwerde eingereicht. Sie verlangen, dass der angefochtene Entscheid aufgehoben und der Regierungsratsbeschluss insofern bestätigt werde, als eine nachträgliche Ausnahmebewilligung für das Schopfgebäude verweigert und dessen Abbruch angeordnet worden sei. Zudem sei der Beschwerdegegner oder seien allenfalls die Vorinstanzen zu verpflichten, in allen vorinstanzlichen Verfahren die Kosten zu tragen und die Beschwerdeführer angemessen zu entschädigen. B._ und das Amt für Raumplanung des Kantons Schwyz stellen den Antrag, die Verwaltungsgerichtsbeschwerde sei abzuweisen, soweit auf sie eingetreten werden könne. Die Regierungsrat des Kantons Schwyz hat auf einen Antrag verzichtet. Das Verwaltungsgericht des Kantons Schwyz ersucht um Abweisung der Beschwerde. Nach Auffassung des Bundesamtes für Raumentwicklung ist die Verwaltungsgerichtsbeschwerde gutzuheissen, sofern die prozessualen Voraussetzungen dazu erfüllt seien. In einem zweiten Schriftenwechsel haben die Parteien an ihren Standpunkten festgehalten. 